Алгоритм 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} }[/math], ..., [math]\displaystyle{ r_{i} }[/math]. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Если A – онлайн-алгоритм для k-серверной задачи, обозначим за [math]\displaystyle{ cost_{A}(\varrho }[/math] ) стоимость плана, производимого алгоритмом A на последовательности запросов , а за opt() – стоимость оптимального плана. Назовем алгоритм A R-конкурентным, если costA() < R – opt() + B, где B – константа, которая может зависеть от M и [math]\displaystyle{ r_{0} }[/math]. Минимальное значение R называется коэффициентом конкурентоспособности A. Разумеется, чем меньше R, тем лучше.

Алгоритм DC-дерева для k серверов на деревьях. Рис. 1 Алгоритм DC-TREE обрабатывает запрос для r. Исходная конфигурация приведена слева; конфигурация после окончания обработки – справа. Вначале все серверы активны. Когда сервер 3 достигает точки x, сервер 1 становится неактивным. Когда сервер 3 достигает точки y, сервер 2 становится неактивным.

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 – дерево, согласно вышеприведенному определению. Пусть даны текущая конфигурация сервера S = {[math]\displaystyle{ s_{1} }[/math], ..., [math]\displaystyle{ s_{k} }[/math]}, где [math]\displaystyle{ s_{k} }[/math] обозначает местоположение сервера j, и точка запроса r; алгоритм выполняет перемещение нескольких серверов, один из которых окажется в результате в точке r. Для двух точек x, y [math]\displaystyle{ \in }[/math] T, обозначим через [x; y] уникальный путь из x в у в дереве T. Сервер j называется активным, если не существует другого сервера в [[math]\displaystyle{ s_{j} }[/math], r] – {[math]\displaystyle{ s_{j} }[/math]}, и j является сервером с минимальным индексом, расположенным в s[math]\displaystyle{ _{j} }[/math] (последнее условие необходимо только для разрыва связей).

Алгоритм DC-TREE По запросу r алгоритм перемещает все активные серверы, непрерывно и с одинаковой скоростью, в направлении r, пока один из серверов не достигнет запроса. Отметим, что в этом процессе некоторые серверы могут стать неактивными; в таком случае они останавливаются. Очевидно, что быстрее других до точки r доберется тот сервер, который был ближе всего к r в момент выдачи запроса r. На рис. 1 представлена работа алгоритма DC-TREE по запросу r. Конкурентный анализ алгоритма DC-TREE основан на рассуждениях о потенциале. Стоимость алгоритма DC-TREE сравнивается со стоимостью алгоритма противоположной стороны, выполняющей запросы на собственных серверах. Обозначим за A конфигурацию серверов «противника» на данном этапе и определим потенциал , где D(S,A) – стоимость алгоритма нахождения соответствия с минимальной стоимостью между S и A. На каждом этапе противная сторона в первую очередь перемещает один из своих серверов в r. На данном под-этапе потенциал возрастает не более чем в k раз по сравнению со стоимостью противной стороны. Затем DC-TREE выполняет запрос. Можно показать, что сумма Ф и стоимости DC-TREE не возрастает. Два этих факта, с учетом накопления по всей последовательности запросов, приводят к следующему результату [4]:

Теорема ([4]) Алгоритм DC-TREE является k-конкурентным на деревьях.

Применение

k-серверная задача представляет собой абстракцию различных задач планирования, включая планирование командных действий при чрезвычайных ситуациях, кэширование в многоуровневых системах памяти и управление движением головки в жестких дисках с двумя головками. Тем не менее, в силу ее абстрактной природы k-серверная задача представляет главным образом теоретический интерес. Алгоритм DC-TREE можно применять для других пространств при помощи «вложения» их в деревья. К примеру, униформное метрическое пространство (в котором все расстояния равны 1) может быть представлено звездой с лучами длины ½ и, следовательно, к нему может быть применен алгоритм DC-TREE. Это также сразу приводит к созданию k-конкурентного алгоритма для задачи кэширования, цель которой заключается в управлении двухуровневой системой памяти, состоящей из большой основной памяти и кэша, способного хранить до k элементов памяти. Если элемент находится в кэше, то стоимость доступа к нему составляет 0, в противном случае стоимость извлечения его из основной памяти равна 1. Задачу кэширования можно рассматривать как k-серверную задачу в униформном метрическом пространстве, в которой позиции серверов представляют элементы, хранящиеся в кэше. Эта идея может быть еще больше расширена на задачу взвешенного кэширования [3], представляющую собой обобщение задачи кэширования, в котором различные элементы могут иметь разную стоимость. Фактически, если удастся вложить метрическое пространство M в дерево, искажение которого будет ограничено δ, тогда алгоритм DC-TREE становится δk-конкурентным алгоритмом для M.

Открытые вопросы

Открытой остается k-серверная гипотеза (состоящая в том, что существует k-конкурентный алгоритм для k серверов в любом метрическом пространстве). Было бы интересно доказать ее для некоторых отдельных случаев – к примеру, для плоскости (как с евклидовой метрикой, так и с манхэттенским расстоянием). k-конкурентный алгоритм для манхэттенской плоскости для k = 2 и k = 3 серверов известен [1], но для k ≥ 4 его не существует. Мало что известно об онлайновых рандомизированных алгоритмах для k-серверов. Фактически даже для k = 2 неизвестно, существует ли рандомизированный алгоритм с коэффициентом конкурентоспособности меньше 2.

См. также

► Детерминистский поиск для линейной задачи

► Обобщенная двухсерверная задача

► Системы метрических задач

► Подкачка и кэширование интернет-страниц

► Подкачка страниц

► Алгоритм рабочей функции для k серверов

Литература

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)