Алгоритм DC-дерева для k серверов на деревьях
Постановка задачи
В рамках k-серверной задачи мы хотим спланировать движение [math]\displaystyle{ k \, }[/math] серверов в метрическом пространстве [math]\displaystyle{ M\, }[/math] в ответ на последовательность [math]\displaystyle{ \varrho = r_{1}, r_{2},...,r_{n} }[/math] запросов, где [math]\displaystyle{ r_{i}\in M }[/math] для каждого [math]\displaystyle{ i\, }[/math].
Вначале все серверы расположены в одной и той же точке [math]\displaystyle{ r_{0}\in M\, }[/math]. После выдачи каждого запроса [math]\displaystyle{ r_{i}\, }[/math] один из [math]\displaystyle{ k\, }[/math] серверов должен переместиться в [math]\displaystyle{ r_{i}\, }[/math]. План определяет, какой сервер перемещается по каждому запросу. Стоимость плана равна сумме расстояний, пройденных серверами, и наша задача заключается в нахождении плана с минимальной стоимостью.
В онлайн-версии k-серверной задачи решение о том, какой сервер должен быть перемещен по каждому запросу [math]\displaystyle{ r_{i}\, }[/math], должно приниматься до выдачи следующего запроса [math]\displaystyle{ r_{i+1}\, }[/math]. Иными словами, выбор этого сервера является функцией от запросов [math]\displaystyle{ r_{1}, r_{2}, ..., r_{i}\, }[/math]. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Если A – онлайн-алгоритм для k-серверной задачи, обозначим за [math]\displaystyle{ cost_{A}(\varrho) }[/math] стоимость плана, производимого алгоритмом A на последовательности запросов [math]\displaystyle{ \varrho }[/math] , а за [math]\displaystyle{ opt(\varrho) }[/math] - стоимость оптимального плана. Назовем алгоритм A R-конкурентным, если [math]\displaystyle{ cost_{A}(\varrho) \lt R \cdot opt(\varrho) + B }[/math], где B – константа, которая может зависеть от M и [math]\displaystyle{ r_{0}\, }[/math]. Минимальное значение R называется коэффициентом конкурентоспособности A. Разумеется, чем меньше R, тем лучше.
k-серверная задача была предложена Манассом, Макгиохом и Слейтором [7, 8], доказавшими, что не существует R-конкурентного онлайн-алгоритма для R < k для любого метрического пространства с не менее чем k + 1 точками. Они также представили 2-конкурентный алгоритм для k = 2 и сформулировали то, что позднее стали называть k-серверной гипотезой, которая утверждает, что существует k-конкурентный онлайн-алгоритм для любого k. Кутсупиас и Пападимитриу [5, 6] доказали, что так называемый алгоритм рабочей функции имеет коэффициент конкурентоспособности не более 2k – 1, и на данный момент это наилучшая известная верхняя граница.
Попытки доказать k-серверную гипотезу привели к открытию k-конкурентных алгоритмов для некоторых ограниченных классов метрических пространств, включая алгоритм DC-TREE для деревьев [4], представленный в следующем разделе. (См. другие примеры в [1, 2, 3]). Дерево представляет собой метрическое пространство, определяемое как связный ациклический граф, дуги которого рассматриваются как отрезки прямых произвольной положительной длины. Это метрическое пространство включает как вершины деревьев, так и точки на дугах, а расстояния измеряются вдоль (уникальных) кратчайших путей.
Основные результаты
Пусть T – дерево, согласно вышеприведенному определению. Пусть даны текущая конфигурация сервера [math]\displaystyle{ S =\, }[/math] { [math]\displaystyle{ s_{1}, ..., s_{k}\, }[/math]}, где [math]\displaystyle{ s_{j}\, }[/math] обозначает местоположение сервера j, и точка запроса r; алгоритм выполняет перемещение нескольких серверов, один из которых окажется в результате в точке r. Для двух точек [math]\displaystyle{ x, y \in T\, }[/math] обозначим через [x, y] уникальный путь из x в у в дереве T. Сервер j называется активным, если не существует другого сервера в [[math]\displaystyle{ s_{j} }[/math], r] – {[math]\displaystyle{ s_{j} }[/math]}, и j является сервером с минимальным индексом, расположенным в [math]\displaystyle{ s_{j} }[/math] (последнее условие необходимо только для разрыва связей).
Алгоритм DC-TREE
По запросу r алгоритм перемещает все активные серверы, непрерывно и с одинаковой скоростью, в направлении r, пока один из серверов не достигнет запроса. Отметим, что в этом процессе некоторые серверы могут стать неактивными; в таком случае они останавливаются. Очевидно, что быстрее других до точки r доберется тот сервер, который был ближе всего к r в момент выдачи запроса r. На иллюстрации представлена работа алгоритма DC-TREE по запросу r.
Алгоритм DC-TREE обрабатывает запрос для r. Исходная конфигурация приведена слева; конфигурация после окончания обработки – справа. Вначале все серверы активны. Когда сервер 3 достигает точки x, сервер 1 становится неактивным. Когда сервер 3 достигает точки y, сервер 2 становится неактивным.
Конкурентный анализ алгоритма DC-TREE основан на рассуждениях о потенциале. Стоимость алгоритма DC-TREE сравнивается со стоимостью алгоритма противоположной стороны, выполняющей запросы на собственных серверах. Обозначим за A конфигурацию серверов «противника» на данном этапе и определим потенциал [math]\displaystyle{ \Phi\ = k \cdot D(S,A) + \sum_{i\lt j}d(s_{i}, s_{j}) }[/math], где [math]\displaystyle{ D(S,A) \, }[/math] – стоимость алгоритма нахождения соответствия с минимальной стоимостью между S и A. На каждом этапе противная сторона в первую очередь перемещает один из своих серверов в r. На данном под-этапе потенциал возрастает не более чем в k раз по сравнению со стоимостью противной стороны. Затем DC-TREE выполняет запрос. Можно показать, что сумма [math]\displaystyle{ \Phi\ }[/math] и стоимости DC-TREE не возрастает. Два этих факта, с учетом накопления по всей последовательности запросов, приводят к следующему результату [4]:
Теорема: Алгоритм DC-TREE является k-конкурентным на деревьях.
Применение
k-серверная задача представляет собой абстракцию различных задач планирования, включая планирование командных действий при чрезвычайных ситуациях, кэширование в многоуровневых системах памяти и управление движением головки в жестких дисках с двумя головками. Тем не менее, в силу ее абстрактной природы k-серверная задача представляет главным образом теоретический интерес. Алгоритм DC-TREE можно применять для других пространств при помощи «вложения» их в деревья. К примеру, униформное метрическое пространство (в котором все расстояния равны 1) может быть представлено звездой с лучами длины 1/2 и, следовательно, к нему может быть применен алгоритм DC-TREE. Это также сразу приводит к созданию k-конкурентного алгоритма для задачи кэширования, цель которой заключается в управлении двухуровневой системой памяти, состоящей из большой основной памяти и кэша, способного хранить до k элементов памяти. Если элемент находится в кэше, то стоимость доступа к нему составляет 0, в противном случае стоимость извлечения его из основной памяти равна 1. Задачу кэширования можно рассматривать как k-серверную задачу в униформном метрическом пространстве, в которой позиции серверов представляют элементы, хранящиеся в кэше. Эта идея может быть еще больше расширена на задачу взвешенного кэширования [3], представляющую собой обобщение задачи кэширования, в котором различные элементы могут иметь разную стоимость. Фактически, если удастся вложить метрическое пространство M в дерево, искажение которого будет ограничено [math]\displaystyle{ \delta }[/math], тогда алгоритм DC-TREE становится [math]\displaystyle{ \delta k }[/math]-конкурентным алгоритмом для M.
Открытые вопросы
Открытой остается k-серверная гипотеза (состоящая в том, что существует k-конкурентный алгоритм для k серверов в любом метрическом пространстве). Было бы интересно доказать ее для некоторых отдельных случаев – к примеру, для плоскости (как с евклидовой метрикой, так и с манхэттенским расстоянием). k-конкурентный алгоритм для манхэттенской плоскости для k = 2 и k = 3 серверов известен [1], но для k ≥ 4 его не существует. Мало что известно об онлайновых рандомизированных алгоритмах для k-серверов. Фактически даже для k = 2 неизвестно, существует ли рандомизированный алгоритм с коэффициентом конкурентоспособности меньше 2.
См. также
Литература
1. Bein, W., Chrobak, M., Larmore, L.L.: The 3-server problem in the plane. Theor. Comput. Sci. 287, 387-391 (2002)
2. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)
3. Chrobak, M., Karloff, H., Payne, T.H., Vishwanathan, S.: New re sults on server problems. SIAM J. Discret. Math. 4, 172-181 (1991)
4. Chrobak, M., Larmore, L.L.: An optimal online algorithm for k servers on trees. SIAM J. Comput. 20,144-148 (1991)
5. Koutsoupias, E., Papadimitriou, C.: On the k-server conjecture. In: Proc. 26th Symp. Theory of Computing (STOC), pp. 507-511. ACM(1994)
6. Koutsoupias, E., Papadimitriou, C.: On the k-server conjecture. J.ACM 42,971-983 (1995)
7. Manasse, M., McGeoch, L.A., Sleator, D.: Competitive algorithms for online problems. In: Proc. 20th Symp. Theory of Computing (STOC), pp. 322-333. ACM (1988)
8. Manasse, M., McGeoch, L.A., Sleator, D.: Competitive algorithms for server problems. J. Algorithms 11, 208-230 (1990)