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

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


[[Файл:WFA.png]]

Рис. 1. План для 2 серверов на последовательности запросов <math>\rho = r_1, r_2, ..., r_7</math>. Изначальная конфигурация равна <math>X_0 = \{ x_1, x_2 \}</math>. Сервер 1 обслуживает запросы <math>r_1, r_2, r_5, r_6</math>, сервер 2 – запросы <math>r_3, r_4, r_7</math>. Стоимость этого плана составляет <math>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>\mathbb{M}, X_0</math> и полная последовательность запросов <math>\rho</math>, оптимальный план можно вычислить за полиномиальное время [6].


В ''онлайновой'' версии k-серверной задачи решение о том, какому серверу следует переместиться для каждого запроса <math>r_i</math>, должно приниматься до выдачи следующего запроса <math>r_{i + 1}</math>. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Обозначим за <math>cost_{\mathcal{A}}(\rho)</math> стоимость плана, производимого онлайн-алгоритмом <math>\mathcal{A}</math> для k-серверной задачи на последовательности запросов <math>\rho</math>, а за <math>opt(\rho)</math> – стоимость оптимального плана на этой последовательности. Назовем алгоритм <math>\mathcal{A}</math> ''R-конкурентным'', если <math>cost_{\mathcal{A}}(\rho) \le R \cdot opt(\rho) + B</math>, где B – константа, которая может зависеть от <math>\mathbb{M}</math> и <math>X_0</math>. Минимальное значение R называется ''коэффициентом конкурентоспособности'' <math>\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>\rho</math> и k-серверной конфигурации X обозначим за <math>\omega_{\rho}(X)</math> минимальную стоимость обслуживания <math>\rho</math> с учетом ограничения, согласно которому по окончании работы алгоритма конфигурацией должна быть X. (Предположим, что начальная конфигурация <math>X_0</math> фиксирована). Функция <math>\omega_{\rho}(\cdot)</math> называется ''рабочей функцией'' для последовательности запросов <math>\rho</math>.


'''Алгоритм WFA'''

Обозначим за <math>\sigma</math> последовательность прошлых запросов и предположим, что текущая конфигурация серверов имеет вид <math>S = \{s_1, s_2, ..., s_k \}</math>, где <math>s_j</math> – местоположение j-го сервера. Пусть r – новый запрос. Выберем <math>s_j \in S</math>, для которого величина <math>\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>k \ge 3</math> k-конкурентные онлайновые k-серверные алгоритмы известны только для некоторых ограниченных метрических пространств, включая деревья [7], метрические пространства с числом точек до k + 2, а также манхэттенскую плоскость для k = 3 (см. [2, 6, 12]). Поскольку анализ алгоритма WFA для общего случая представляется сложным, любопытно было бы доказать его k-конкурентность для некоторых отдельных случаев – например, на плоскости (с любой разумной метрикой) для <math>k \ge 4</math> серверов.


Мало что известно о коэффициенте конкурентоспособности 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)