Обобщенная двухсерверная задача: различия между версиями

В обобщенной двухсерверной задаче имеются два сервера, один из которых перемещается в метрическом пространстве <math>\mathbb{X} \;</math>, а другой – в метрическом пространстве <math>\mathbb{Y} \;</math>. Они обслуживают запросы <math>r \in \mathbb{X} \times \mathbb{Y} \;</math>, которые поступают один за одним. Запрос r = (x, y) обслуживается посредством перемещения <math>\mathbb{X}</math>-сервера в точку x либо <math>\mathbb{Y}</math>-сервера в точку y. Решение, какой из двух серверов переместить при следующем запросе, не подлежит отмене и принимается в отсутствие каких-либо знаний о будущих запросах. Задача заключается в минимизации расстояния, пройденного обоими серверами.

Рис. 1. В этом примере оба сервера перемещаются по плоскости и начинают движение с конфигурации (<math>x_0, y_0 \;</math>). <math>\mathbb{X}</math>-сервер перемещается при выполнении запросов 1 и 3, <math>\mathbb{Y}</math>-сервер обслуживает запросы 2 и 4. Стоимость решения представляет собой сумму длин путей

 

Стандартный алгоритм, который доказуемо эффективно справляется с несколькими элементарными задачами маршрутизации – это так называемый ''алгоритм рабочей функции'' [2, 6, 8]. После каждого запроса алгоритм перемещается в конфигурацию с низкой стоимостью, находящуюся не слишком далеко от текущей конфигурации. Точнее говоря, если после обслуживания последовательности <math>\sigma \;</math> система имеет конфигурацию C, а <math>r \subseteq \mathbb{M} \;</math> – следующий запрос, то алгоритм рабочей функции с параметром <math>\lambda \ge 1 \;</math> переходит к конфигурации <math>C' \in r \;</math>, которая минимизирует соотношение <math>\lambda W_{\sigma, r} (C') + d(C, C') \;</math>, где d(C, C') – расстояние между конфигурациями C и C', а <math>W_{\sigma, r} (C') \;</math> – стоимость оптимального решения, обслуживающего все запросы (по порядку) в <math>\sigma \;</math> плюс запрос r с тем ограничением, что оно завершает работу в конфигурации C'.

Основным результатом работы [11] является достаточное условие наличия константно-конкурентного алгоритма для метрической системы сервисов. Кроме того, авторы продемонстрировали, что это условие выполняется и для обобщенной двухсерверной задачи.

 

 

Для фиксированной метрической системы сервисов S с метрическим пространством <math>\mathbb{M} \;</math> обозначим за <math>A(C, \sigma) \;</math> стоимость работы алгоритма A на входной последовательности <math>\sigma \;</math>, начинающего работу с конфигурации C. Пусть <math>OPT(C, \sigma) \;</math> – стоимость соответствующего оптимального решения. Мы говорим, что путь T в <math>\mathbb{M} \;</math> ''обслуживает'' последовательность <math>\sigma \;</math>, если он посещает все запросы по порядку. Следовательно, допустимым путем является такой путь, который обслуживает всю последовательность и начинается с исходной конфигурации.

Пути <math>T_1 \;</math> и <math>T_2 \;</math> называются ''независимыми'', если они разделены следующим образом: <math>|T_1| + |T_2| < d(C^s_1, C^t_2) + d(C^s_2, C^t_1) \;</math>, где <math>C_i^s \;</math> и <math>C_i^t \;</math> – начальная и конечная точки пути <math>T_i \; (i \in \{ 1, 2 \})</math>, соответственно. Заметим, в частности, что пересекающиеся пути не являются независимыми.

'''Теорема 1. Пусть S – метрическая система сервисов с метрическим пространством <math>\mathbb{M} \;</math>. Предположим, что существует алгоритм A и константы <math>\alpha \ge 1, \beta \ge 0, m \ge 2 \;</math>, такие, что для любой точки <math>C \in \mathbb{M} \;</math>, последовательности <math>\sigma \;</math> и попарно независимых путей <math>T_1, T_2, ... , T_m \;</math>, обслуживающих <math>\sigma \;</math>, выполняется соотношение'''

'''Тогда существует алгоритм B, являющийся константно-конкурентным для S.'''

Для обобщенной двухсерверной задачи так называемый ''алгоритм баланса'' удовлетворяет условию (1). Этот алгоритм сохраняет кумулятивную стоимость обоих серверов и при получении каждого запроса перемещает тот сервер, при котором максимум двух новых значений будет минимальным. Сам по себе алгоритм баланса не является константно-конкурентным, однако, согласно теореме 1, если мы рационально объединим его с алгоритмом рабочей функции, мы получим константно-конкурентный алгоритм.

Множество метрических систем сервисов можно объединить, получив так называемую ''систему сумм'' [9]. Запрос к системе сумм включает по одному запросу к каждой системе, и для его обслуживания необходимо обслужить по меньшей мере один из отдельных запросов. Обобщенная двухсерверная задача может рассматриваться как одна из самых простых систем сумм, поскольку две отдельных задачи являются совершенно тривиальными: имеется один сервер, и каждый запрос состоит из одного пункта.

* [[Онлайн-алгоритм подкачки и кэширования]]