4446
правок
Алгоритм DC-дерева для k серверов на деревьях: различия между версиями
Материал из WEGA
Алгоритм DC-дерева для k серверов на деревьях (посмотреть исходный код)
Версия от 13:32, 16 декабря 2011
, 16 декабря 2011нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 40: | Строка 40: | ||
k-серверная задача представляет собой абстракцию различных задач планирования, включая планирование командных действий при чрезвычайных ситуациях, кэширование в многоуровневых системах памяти и управление движением головки в жестких дисках с двумя головками. Тем не менее, в силу ее абстрактной природы k-серверная задача представляет главным образом теоретический интерес. | k-серверная задача представляет собой абстракцию различных задач планирования, включая планирование командных действий при чрезвычайных ситуациях, кэширование в многоуровневых системах памяти и управление движением головки в жестких дисках с двумя головками. Тем не менее, в силу ее абстрактной природы k-серверная задача представляет главным образом теоретический интерес. | ||
Алгоритм DC-TREE можно применять для других пространств при помощи «вложения» их в деревья. К примеру, униформное метрическое пространство (в котором все расстояния равны 1) может быть представлено звездой с лучами длины 1/2 и, следовательно, к нему может быть применен алгоритм DC-TREE. Это также сразу приводит к созданию k-конкурентного алгоритма для ''задачи кэширования'', цель которой заключается в управлении двухуровневой системой памяти, состоящей из большой основной памяти и кэша, способного хранить до k элементов памяти. Если элемент находится в кэше, то стоимость доступа к нему составляет 0, в противном случае стоимость извлечения его из основной памяти равна 1. Задачу кэширования можно рассматривать как k-серверную задачу в униформном метрическом пространстве, в которой позиции серверов представляют элементы, хранящиеся в кэше. Эта идея может быть еще больше расширена на задачу ''взвешенного кэширования'' [3], представляющую собой обобщение задачи кэширования, в котором различные элементы могут иметь разную стоимость. Фактически, если удастся вложить метрическое пространство M в дерево, искажение которого будет ограничено | Алгоритм DC-TREE можно применять для других пространств при помощи «вложения» их в деревья. К примеру, униформное метрическое пространство (в котором все расстояния равны 1) может быть представлено звездой с лучами длины 1/2 и, следовательно, к нему может быть применен алгоритм DC-TREE. Это также сразу приводит к созданию k-конкурентного алгоритма для ''задачи кэширования'', цель которой заключается в управлении двухуровневой системой памяти, состоящей из большой основной памяти и кэша, способного хранить до k элементов памяти. Если элемент находится в кэше, то стоимость доступа к нему составляет 0, в противном случае стоимость извлечения его из основной памяти равна 1. Задачу кэширования можно рассматривать как k-серверную задачу в униформном метрическом пространстве, в которой позиции серверов представляют элементы, хранящиеся в кэше. Эта идея может быть еще больше расширена на задачу ''взвешенного кэширования'' [3], представляющую собой обобщение задачи кэширования, в котором различные элементы могут иметь разную стоимость. Фактически, если удастся вложить метрическое пространство M в дерево, искажение которого будет ограничено <math>\delta </math>, тогда алгоритм DC-TREE становится <math>\delta k</math>-конкурентным алгоритмом для M. | ||
| Строка 46: | Строка 46: | ||
Открытой остается k-серверная гипотеза (состоящая в том, что существует k-конкурентный алгоритм для k серверов в любом метрическом пространстве). Было бы интересно доказать ее для некоторых отдельных случаев – к примеру, для плоскости (как с евклидовой метрикой, так и с манхэттенским расстоянием). k-конкурентный алгоритм для манхэттенской плоскости для k = 2 и k = 3 серверов известен [1], но для k ≥ 4 его не существует. | Открытой остается k-серверная гипотеза (состоящая в том, что существует k-конкурентный алгоритм для k серверов в любом метрическом пространстве). Было бы интересно доказать ее для некоторых отдельных случаев – к примеру, для плоскости (как с евклидовой метрикой, так и с манхэттенским расстоянием). k-конкурентный алгоритм для манхэттенской плоскости для k = 2 и k = 3 серверов известен [1], но для k ≥ 4 его не существует. | ||
Мало что известно об онлайновых рандомизированных алгоритмах для k-серверов. Фактически даже для k = 2 неизвестно, существует ли рандомизированный алгоритм с коэффициентом конкурентоспособности меньше 2. | Мало что известно об онлайновых ''рандомизированных'' алгоритмах для k-серверов. Фактически даже для k = 2 неизвестно, существует ли рандомизированный алгоритм с коэффициентом конкурентоспособности меньше 2. | ||
