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

Обобщенная двухсерверная задача относится к классу задач маршрутизации под названием ''систем метрических сервисов'' [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>.

При моделировании обобщенной двухсерверной задачи системой метрических сервисов мы получаем <math>\mathbb{M} = \mathbb{X} \times \mathbb{Y}</math> и <math>\mathcal{R} = \{ \{ x \times \mathbb{Y} \} \cup \{ \mathbb{X} \times y \} | x \in \mathbb{X}, y \in \mathbb{Y} \}</math>. В классической двухсерверной задаче оба сервера перемещаются в одном и том же пространстве и получают одни и те же запросы, т.е. <math>\mathbb{M} = \mathbb{X} \times \mathbb{X}</math> и <math>\mathcal{R} = \{ \{ x \times \mathbb{X} \} \cup \{ \mathbb{X} \times x \} | x \in \mathbb{X} \}</math>.

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

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

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