Алгоритм рабочей функции для k серверов
Постановка задачи
В рамках k-серверной задачи мы хотим спланировать движение k серверов в метрическом пространстве [math]\displaystyle{ \mathbb{M} }[/math] в ответ на последовательность запросов [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 серверов на последовательности запросов [math]\displaystyle{ \rho = r_1, r_2, ..., r_7 }[/math]. Изначальная конфигурация равна [math]\displaystyle{ X_0 = \{ x_1, x_2 \} }[/math]. Сервер 1 обслуживает запросы [math]\displaystyle{ r_1, r_2, r_5, r_6 }[/math], сервер 2 – запросы [math]\displaystyle{ r_3, r_4, r_7 }[/math]. Стоимость этого плана составляет [math]\displaystyle{ d(x_1, r_1) + d(r_1, r_2) + d(r_2, r_5) + d(r_5, r_6) + d(x_2, r_3) + d(r_3, r_4) + d(r_4, r_7) }[/math], где d(x, y) обозначает расстояние между точками x и y
В оффлайновом случае, когда даны [math]\displaystyle{ \mathbb{M}, X_0 }[/math] и полная последовательность запросов [math]\displaystyle{ \rho }[/math], оптимальный план можно вычислить за полиномиальное время [6].
В онлайновой версии k-серверной задачи решение о том, какому серверу следует переместиться для каждого запроса [math]\displaystyle{ r_i }[/math], должно приниматься до выдачи следующего запроса [math]\displaystyle{ r_{i + 1} }[/math]. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Обозначим за [math]\displaystyle{ cost_{\mathcal{A}}(\rho) }[/math] стоимость плана, производимого онлайн-алгоритмом [math]\displaystyle{ \mathcal{A} }[/math] для k-серверной задачи на последовательности запросов [math]\displaystyle{ \rho }[/math], а за [math]\displaystyle{ opt(\rho) }[/math] – стоимость оптимального плана на этой последовательности. Назовем алгоритм [math]\displaystyle{ \mathcal{A} }[/math] R-конкурентным, если [math]\displaystyle{ cost_{\mathcal{A}}(\rho) \le R \cdot opt(\rho) + B }[/math], где B – константа, которая может зависеть от [math]\displaystyle{ \mathbb{M} }[/math] и [math]\displaystyle{ X_0 }[/math]. Минимальное значение R называется коэффициентом конкурентоспособности [math]\displaystyle{ \mathcal{A} }[/math]. Разумеется, чем меньше R, тем лучше.
k-серверная задача была предложена Манассом, Макгиохом и Слейтором [13,14], доказавшими, что ни один (детерминированный) онлайн-алгоритм не может достичь коэффициента конкурентоспособности меньше k для любого метрического пространства с не менее чем k + 1 точками. Они также представили 2-конкурентный алгоритм для k = 2 и сформулировали то, что позднее стали называть k-серверной гипотезой, которая утверждает, что существует k-конкурентный онлайн-алгоритм для любого k. Кутсупиас и Пападимитриу [10, 11] (см. также [3, 8, 9]) доказали, что так называемый алгоритм рабочей функции, представленный далее, имеет коэффициент конкурентоспособности не более 2k – 1, и на данный момент это наилучшая известная верхняя граница.
Основные результаты
Идея алгоритма рабочей функции заключается в нахождении баланса между двумя жадными стратегиями при выдаче нового запроса. Первая из них заключается в обслуживании запроса при помощи ближайшего сервера. Вторая пытается следовать оптимальному плану. Грубо говоря, из k возможных новых конфигураций эта стратегия выбирает ту, в которой в это время должен был оптимальный план, если бы других невыданных запросов не осталось.
Формально, для каждой последовательности запросов [math]\displaystyle{ \rho }[/math] и k-серверной конфигурации X обозначим за [math]\displaystyle{ \omega_{\rho}(X) }[/math] минимальную стоимость обслуживания [math]\displaystyle{ \rho }[/math] с учетом ограничения, согласно которому по окончании работы алгоритма конфигурацией должна быть X. (Предположим, что начальная конфигурация [math]\displaystyle{ X_0 }[/math] фиксирована). Функция [math]\displaystyle{ \omega_{\rho}(\cdot) }[/math] называется рабочей функцией для последовательности запросов [math]\displaystyle{ \rho }[/math].
Алгоритм WFA
Обозначим за [math]\displaystyle{ \sigma }[/math] последовательность прошлых запросов и предположим, что текущая конфигурация серверов имеет вид [math]\displaystyle{ S = \{s_1, s_2, ..., s_k \} }[/math], где [math]\displaystyle{ s_j }[/math] – местоположение j-го сервера. Пусть r – новый запрос. Выберем [math]\displaystyle{ s_j \in S }[/math], для которого величина [math]\displaystyle{ \omega_{\sigma \rho}(S - \{ s_j \} \cup \{ r \}) + d(s_j, r) }[/math] минимальна, и переместим сервер j к r.
Теорема 1 ([10,11]). Алгоритм WFA является (2k - 1)-конкурентным.
Применение
k-серверную задачу можно рассматривать как абстракцию онлайновых задач, возникающих при планировании командных действий при чрезвычайных ситуациях, кэшировании (или подкачке) в двухуровневых системах памяти, управлении движением головки в жестких дисках и других случаях. Однако в своей абстрактной форме она представляет главным образом теоретический интерес.
Алгоритм WFA может применяться к некоторым обобщениям k-серверной задачи. В частности, он является (2n - 1)-конкурентным для систем метрических задач с n состояниями, соответствуя нижней границе [3, 4, 8]. См. другие примеры и расширения в [1, 3, 5].
Открытые вопросы
Теорема 1 подходит исключительно близко к доказательству k-серверной гипотезы, описанной ранее. Была даже высказано предположение, что сам алгоритм WFA является k-конкурентным для k серверов, однако доказать его пока не удалось.
Для [math]\displaystyle{ k \ge 3 }[/math] k-конкурентные онлайновые k-серверные алгоритмы известны только для некоторых ограниченных метрических пространств, включая деревья [7], метрические пространства с числом точек до k + 2, а также манхэттенскую плоскость для k = 3 (см. [2, 6, 12]). Поскольку анализ алгоритма WFA для общего случая представляется сложным, любопытно было бы доказать его k-конкурентность для некоторых отдельных случаев – например, на плоскости (с любой разумной метрикой) для [math]\displaystyle{ k \ge 4 }[/math] серверов.
Мало что известно о коэффициенте конкурентоспособности k-серверной задачи для рандомизированного случая. Фактически неизвестно даже, можно ли получить коэффициент лучше 2 для k = 2.
См. также
Литература
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)
