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

Постановка задачи

В рамках k-серверной задачи мы хотим спланировать движение k серверов в метрическом пространстве M в ответ на последовательность [math]\displaystyle{ \rho = r_1, r_2, ..., r_n }[/math] запросов, где [math]\displaystyle{ r_i \in M }[/math] для каждого i. Вначале все серверы занимают одну и ту же конфигурацию [math]\displaystyle{ X_0 \subseteq \mathbb{M} }[/math]. После выдачи каждого запроса [math]\displaystyle{ r_i }[/math] один из k серверов должен переместиться в [math]\displaystyle{ r_i }[/math]. План S определяет, какой сервер перемещается по каждому запросу. Задача заключается в создании плана минимальной стоимости, где стоимость плана равна сумме расстояний, пройденных серверами. Ниже приводится пример плана для 2 серверов на последовательности запросов.

Рис. 1. План для 2 серверов на последовательности запросов % = r1 ;r2... r7. Изначальная конфигурация равна X0 = fx1;x2g. Сервер 1 обслуживает запросы r1, r2, r5, r6, сервер 2 – запросы r3, r4, r7. Стоимость этого плана составляет d(x1, r1) + d(r1, r2) + d(r2, r5) + d(r5, r6) + d(x2, r3) + d(r3, r4) + d(r4, r7), где d(x, y) обозначает расстояние между точками x и y

В оффлайновом случае, когда даны M, X0 и полная последовательность запросов %, оптимальный план можно вычислить за полиномиальное время [6].

В онлайн-версии k-серверной задачи решение о том, к какому серверу следует переместиться для каждого запроса ri, должно приниматься до выдачи следующего запроса ri+1. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Обозначим за costA(*) стоимость плана, производимого онлайн-алгоритмом A для k-серверной задачи на последовательности запросов *, а за opt(*) – стоимость оптимального плана на этой последовательности. Назовем алгоритм A R-конкурентным, если costA(*) < R – opt(*) + B, где B – константа, которая может зависеть от M и X0. Минимальное значение R называется коэффициентом конкурентоспособности A. Разумеется, чем меньше R, тем лучше.

k-серверная задача была предложена Манассом, Макгиохом и Слейтором [13,14], доказавшими, что ни один (детерминированный) онлайн-алгоритм не может достичь коэффициента конкурентоспособности меньше k для любого метрического пространства с не менее чем k + 1 точками. Они также представили 2-конкурентный алгоритм для k = 2 и сформулировали то, что позднее стали называть k-серверной гипотезой, которая утверждает, что существует k-конкурентный онлайн-алгоритм для любого k. Кутсупиас и Пападимитриу [10, 11] (см. также [3, 8, 9]) доказали, что так называемый алгоритм рабочей функции, представленный далее, имеет коэффициент конкурентоспособности не более 2k – 1, и на данный момент это наилучшая известная верхняя граница.

Основные результаты

Идея алгоритма рабочей функции заключается в нахождении баланса между двумя жадными стратегиями при выдаче нового запроса. Первая из них заключается в обслуживании запроса при помощи ближайшего сервера. Вторая пытается найти оптимальный план. Грубо говоря, из k возможных новых конфигураций эта стратегия выбирает ту, в которой в это время имеется оптимальный план, если других невыданных запросов не осталось.

Формально, для каждой последовательности запросов % и k-серверной конфигурации X обозначим за!%(X) минимальную стоимость обслуживания % с учетом ограничения, согласно которому по окончании работы алгоритма конфигурацией должна быть X. (Предположим, что начальная конфигурация X0 фиксирована). Функция ше{-) называется рабочей функцией для последовательности запросов %.

Алгоритм WFA Обозначим за a последовательность прошлых запросов и предположим, что текущая конфигурация серверов имеет видS = fs1, s2, …, sk g, гдк sj – местоположение j-го сервера. Пусть r – новый запрос. Выберем sj 2 S, для которого величина «<jr(S — {SJ} U {r}) + d(sj, r) минимальна, и переместим сервер j к r.

Теорема 1 ([10,11]). Алгоритм WFA является (2k- ^-конкурентным.

Применение

k-серверную задачу можно рассматривать как абстракцию онлайновых задач, возникающих при планировании командных действий при чрезвычайных ситуациях, кэшировании (или подкачке) в двухуровневых системах памяти, управлении движением головки в жестких дисках и других случаях. Однако в своей абстрактной форме она представляет главным образом теоретический интерес.

Алгоритм WFA может применяться к некоторым обобщениям k-серверной задачи. В частности, он является (2 n - 1)-конкурентным для систем метрических задач с n состояниями, соответствуя нижней границе [3, 4, 8]. См. другие примеры и расширения в [1, 3, 5].

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

Теорема 1 подходит исключительно близко к доказательству k-серверной гипотезы, описанной ранее. Была даже высказано предположение, что сам алгоритм WFA является k-конкурентными для k серверов, однако доказать его пока не удалось.

Для k > 3 k-конкурентные онлайновые k-серверные алгоритмы известны только для некоторых ограниченных метрических пространств, включая деревья [7], метрические пространства с числом точек до k + 2, а также манхэттенскую плоскость для k = 3 (см. [2, 6, 12]). Поскольку анализ алгоритма Algorithm для общего случая представляется сложным, любопытно было бы доказать его k-конкурентоспособность для некоторых отдельных случаев – например, на плоскости (с любой разумной метрикой) для k > 4 серверов.

Мало что известно о коэффициенте конкурентоспособности k-серверной задачи для рандомизированного случая. Фактически неизвестно даже можно ли получить коэффициент лучше 2 для k = 2.

См. также

• Алгоритм DC-дерева для k серверов на деревьях
• Детерминистский поиск для линейной задачи
• Обобщенная двухсерверная задача
• Системы метрических задач
• Онлайн-алгоритм подкачки и кэширования
• Подкачка страниц

Литература

1. Anderson, E.J., Hildrum, K., Karlin, A.R., Rasala, A., Saks, M.: On list update and work function algorithms. Theor. Comput. Sci. 287,393^18(2002)

2. Bein, W., Chrobak, M., Larmore, L.L.: The 3-server problem in the plane.Theor. Comput. Sci. 287,387-391 (2002)

3. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)

4. Borodin, A., Linial, N., Saks, M.: An optimal online algorithm for metrical task systems. In: Proc. 19th Symp. Theory of Computing (STOC), ACM, pp. 373-382 (1987)

5. Burley, W.R.: Traversing layered graphs using the work function algorithm. J. Algorithms 20,479-511 (1996)

6. Chrobak, M., Karloff, H., Payne, T.H., Vishwanathan, S.: New results on server problems. SIAM J. Discret. Math. 4, 172-181 (1991)

7. Chrobak, M., Larmore, L.L.: An optimal online algorithm for k servers on trees. SIAM J. Comput. 20,144-148(1991)

8. Chrobak, M., Larmore, L.L.: Metrical task systems, the server problem, and the work function algorithm. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms: The State of the Art, pp. 74-94. Springer, London (1998)

9. Koutsoupias, E.: Weak adversaries for the k-server problem. In: Proc. 40th Symp. Foundations of Computer Science (FOCS), IEEE, pp. 444^49 (1999)

10. Koutsoupias, E., Papadimitriou, C.: On the k-server conjecture. In: Proc. 26th Symp. Theory of Computing (STOC), ACM, pp. 507-511 (1994)

11. Koutsoupias, E., Papadimitriou, C.: On the k-server conjecture. J. ACM 42,971-983 (1995)

12. Koutsoupias, E., Papadimitriou, C.: The 2-evader problem. Inf. Proc. Lett. 57, 249-252 (1996)

13. Manasse, M., McGeoch, L.A., Sleator, D.: Competitive algorithms for online problems. In: Proc. 20th Symp. Theory of Computing (STOC), ACM, pp. 322-333 (1988)

14. Manasse, M., McGeoch, L.A., Sleator, D.: Competitive algorithms for server problems. J. Algorithms 11, 208-230 (1990)