Алгоритм DC-дерева для k серверов на деревьях: различия между версиями

В рамках ''k-серверной задачи'' мы хотим спланировать движение <math>k</math> серверов в метрическом пространстве <math>M</math> в ответ на последовательность <math>\varrho = r_{1}, r_{2},...,r_{n}</math>  

запросов, где <math>r_{i}\in M</math>  

для каждого <math>i</math>.  

Вначале все серверы расположены в одной и той же точке <math>r_{0}\in M</math>. После выдачи каждого запроса <math>r_{i}</math> один из <math>k</math> серверов должен переместиться в <math>r_{i}</math>. ''План'' определяет, какой сервер перемещается по каждому запросу. ''Стоимость'' плана равна сумме расстояний, пройденных серверами, и наша задача заключается в нахождении плана с минимальной стоимостью.

В ''онлайн-версии'' k-серверной задачи решение о том, какой сервер должен быть перемещен по каждому запросу <math>r_{i}</math>, должно приниматься до выдачи следующего запроса <math>r_{i+1}</math>. Иными словами, выбор этого сервера является функцией от запросов <math>r_{1}, r_{2}</math>, ..., <math>r_{i}</math>. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Если A – онлайн-алгоритм для k-серверной задачи, обозначим за <math>cost_{A}(\varrho)</math> стоимость плана, производимого алгоритмом A на последовательности запросов <math>\varrho</math>

, а за <math>opt(\varrho)</math> -

стоимость оптимального плана. Назовем алгоритм A ''R-конкурентным'', если <math>cost_{A}(\varrho) < R \cdot opt(\varrho) + B</math>, где B – константа, которая может зависеть от M и <math>r_{0}</math>. Минимальное значение R называется ''коэффициентом конкурентоспособности'' A. Разумеется, чем меньше R, тем лучше.

k-серверная задача была предложена Манассом, Макгиохом и Слейтором [7, 8], доказавшими, что не существует R-конкурентного онлайн-алгоритма для R < k для любого метрического пространства с не менее чем k + 1 точками. Они также представили 2-конкурентный алгоритм для k = 2 и сформулировали то, что позднее стали называть ''k-серверной гипотезой'', которая утверждает, что существует k-конкурентный онлайн-алгоритм для любого k. Кутсупиас и Пападимитриу [5, 6] доказали, что так называемый ''алгоритм рабочей функции'' имеет коэффициент конкурентоспособности не более 2k – 1, и на данный момент это наилучшая известная верхняя граница.

Пусть T – дерево, согласно вышеприведенному определению. Пусть даны текущая конфигурация сервера S = {<math>s_{1}</math>, ..., <math>s_{k}</math>}, где <math>s_{j}</math> обозначает местоположение сервера j, и точка запроса r; алгоритм выполняет перемещение нескольких серверов, один из которых окажется в результате в точке r. Для двух точек x, y <math>\in </math> T, обозначим через [x, y] уникальный путь из x в у в дереве T. Сервер j называется ''активным'', если не существует другого сервера в [<math>s_{j}</math>, r] – {<math>s_{j}</math>}, и j является сервером с минимальным индексом, расположенным в s<math>_{j}</math> (последнее условие необходимо только для разрыва связей).

Теорема ([4]) Алгоритм DC-TREE является k-конкурентным на деревьях.

Алгоритм DC-TREE можно применять для других пространств при помощи «вложения» их в деревья. К примеру, униформное метрическое пространство (в котором все расстояния равны 1) может быть представлено звездой с лучами длины ½ и, следовательно, к нему может быть применен алгоритм DC-TREE. Это также сразу приводит к созданию k-конкурентного алгоритма для задачи кэширования, цель которой заключается в управлении двухуровневой системой памяти, состоящей из большой основной памяти и кэша, способного хранить до k элементов памяти. Если элемент находится в кэше, то стоимость доступа к нему составляет 0, в противном случае стоимость извлечения его из основной памяти равна 1. Задачу кэширования можно рассматривать как k-серверную задачу в униформном метрическом пространстве, в которой позиции серверов представляют элементы, хранящиеся в кэше. Эта идея может быть еще больше расширена на задачу взвешенного кэширования [3], представляющую собой обобщение задачи кэширования, в котором различные элементы могут иметь разную стоимость. Фактически, если удастся вложить метрическое пространство M в дерево, искажение которого будет ограничено δ, тогда алгоритм DC-TREE становится δk-конкурентным алгоритмом для M.

 

Мало что известно об онлайновых рандомизированных алгоритмах для k-серверов. Фактически даже для k = 2 неизвестно, существует ли рандомизированный алгоритм с коэффициентом конкурентоспособности меньше 2.

► [[Детерминистский поиск для линейной задачи]]

► [[Обобщенная двухсерверная задача]]

► [[Системы метрических задач]]

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

► [[Подкачка страниц]]

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