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

В обобщенной двухсерверной задаче имеются два сервера, один из которых перемещается в метрическом пространстве <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. Решение, какой из двух серверов переместить при следующем запросе, не подлежит отменен и принимается в отсутствие каких-либо знаний о будущих запросах. Задача заключается в минимизации расстояния, пройденного обоими серверами.

Обобщенная двухсерверная задача относится к классу задач маршрутизации под названием ''метрической системы сервисов'' [5, 10]. Подобную систему определяют метрическое пространство <math>\mathbb{M} \;</math> всех возможных конфигураций системы, начальная конфигурация <math>C_0 \;</math> и множество <math>\mathcal{R} \;</math> возможных запросов, в котором каждый запрос <math>r \in \mathcal{R} \;</math> является подмножеством <math>\mathbb{M} \;</math>. Пусть дана последовательность запросов <math>r_1, r_2, ..., r_n \;</math>. Допустимым решением является последовательность конфигураций <math>C_1, C_2, ..., C_n \;</math>, такая, что <math>C_i \in r_i \;</math> для всех <math>i \in \{ 1, ..., n \} \;</math>.

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

Для фиксированной метрической системы сервисов 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>, если он посещает все запросы по порядку. Следовательно, допустимым путем является такой путь, который обслуживает все запросы и начинается с исходной конфигурации.

Теорема 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>, выполняется соотношение

A(C, a) < aOPT(C, a) +

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

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

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

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