4446
правок
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) м (→См. также) |
||
(не показано 5 промежуточных версий этого же участника) | |||
Строка 18: | Строка 18: | ||
Пусть T – дерево, согласно вышеприведенному определению. Пусть даны текущая конфигурация сервера S = {<math>s_{1} | Пусть T – дерево, согласно вышеприведенному определению. Пусть даны текущая конфигурация сервера <math>S =\, </math> { <math>s_{1}, ..., s_{k}\, </math>}, где <math>s_{j}\, </math> обозначает местоположение сервера j, и точка запроса r; алгоритм выполняет перемещение нескольких серверов, один из которых окажется в результате в точке r. Для двух точек <math>x, y \in T\, </math> обозначим через [x, y] уникальный путь из x в у в дереве T. Сервер j называется ''активным'', если не существует другого сервера в [<math>s_{j}</math>, r] – {<math>s_{j}</math>}, и j является сервером с минимальным индексом, расположенным в <math>s_{j}</math> (последнее условие необходимо только для разрыва связей). | ||
'''Алгоритм DC-TREE''' | '''Алгоритм DC-TREE''' | ||
Строка 30: | Строка 30: | ||
'' | '' | ||
Конкурентный анализ алгоритма DC-TREE основан на рассуждениях о потенциале. Стоимость алгоритма DC-TREE сравнивается со стоимостью алгоритма противоположной стороны, выполняющей запросы на собственных серверах. Обозначим за A конфигурацию серверов «противника» на данном этапе и определим потенциал <math>\Phi\ = k \cdot D(S,A) + \sum_{i<j}d(s_{i}, s_{j})</math> | |||
, где D(S,A) – стоимость алгоритма нахождения соответствия с минимальной стоимостью между S и A. На каждом этапе противная сторона в первую очередь перемещает один из своих серверов в r. На данном под-этапе потенциал возрастает не более чем в k раз по сравнению со стоимостью противной стороны. Затем DC-TREE выполняет запрос. Можно показать, что сумма <math>\Phi\ </math> и стоимости DC-TREE не возрастает. Два этих факта, с учетом накопления по всей последовательности запросов, приводят к следующему результату [4]: | Конкурентный анализ алгоритма DC-TREE основан на рассуждениях о потенциале. Стоимость алгоритма DC-TREE сравнивается со стоимостью алгоритма противоположной стороны, выполняющей запросы на собственных серверах. Обозначим за A конфигурацию серверов «противника» на данном этапе и определим потенциал <math>\Phi\ = k \cdot D(S,A) + \sum_{i<j}d(s_{i}, s_{j})</math>, где <math>D(S,A) \, </math> – стоимость алгоритма нахождения соответствия с минимальной стоимостью между S и A. На каждом этапе противная сторона в первую очередь перемещает один из своих серверов в r. На данном под-этапе потенциал возрастает не более чем в k раз по сравнению со стоимостью противной стороны. Затем DC-TREE выполняет запрос. Можно показать, что сумма <math>\Phi\ </math> и стоимости DC-TREE не возрастает. Два этих факта, с учетом накопления по всей последовательности запросов, приводят к следующему результату [4]: | ||
'''Теорема: Алгоритм DC-TREE является k-конкурентным на деревьях.''' | '''Теорема: Алгоритм DC-TREE является k-конкурентным на деревьях.''' | ||
Строка 38: | Строка 38: | ||
k-серверная задача представляет собой абстракцию различных задач планирования, включая планирование командных действий при чрезвычайных ситуациях, кэширование в многоуровневых системах памяти и управление движением головки в жестких дисках с двумя головками. Тем не менее, в силу ее абстрактной природы k-серверная задача представляет главным образом теоретический интерес. | k-серверная задача представляет собой абстракцию различных задач планирования, включая планирование командных действий при чрезвычайных ситуациях, кэширование в многоуровневых системах памяти и управление движением головки в жестких дисках с двумя головками. Тем не менее, в силу ее абстрактной природы k-серверная задача представляет главным образом теоретический интерес. | ||
Алгоритм DC-TREE можно применять для других пространств при помощи «вложения» их в деревья. К примеру, униформное метрическое пространство (в котором все расстояния равны 1) может быть представлено звездой с лучами длины 1/2 и, следовательно, к нему может быть применен алгоритм DC-TREE. Это также сразу приводит к созданию k-конкурентного алгоритма для | Алгоритм DC-TREE можно применять для других пространств при помощи «вложения» их в деревья. К примеру, униформное метрическое пространство (в котором все расстояния равны 1) может быть представлено звездой с лучами длины 1/2 и, следовательно, к нему может быть применен алгоритм DC-TREE. Это также сразу приводит к созданию k-конкурентного алгоритма для [[кэширование|задачи кэширования]], цель которой заключается в управлении двухуровневой системой памяти, состоящей из большой основной памяти и кэша, способного хранить до k элементов памяти. Если элемент находится в кэше, то стоимость доступа к нему составляет 0, в противном случае стоимость извлечения его из основной памяти равна 1. Задачу кэширования можно рассматривать как k-серверную задачу в униформном метрическом пространстве, в которой позиции серверов представляют элементы, хранящиеся в кэше. Эта идея может быть еще больше расширена на задачу [[взвешенное кэширование|взвешенного кэширования]] [3], представляющую собой обобщение задачи кэширования, в котором различные элементы могут иметь разную стоимость. Фактически, если удастся вложить метрическое пространство M в дерево, искажение которого будет ограничено <math>\delta </math>, тогда алгоритм DC-TREE становится <math>\delta k</math>-конкурентным алгоритмом для M. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Строка 49: | Строка 48: | ||
== См. также == | == См. также == | ||
* ''[[ | * ''[[Детерминированный алгоритм поиска на прямой]]'', | ||
* ''[[Обобщенная двухсерверная задача]]'', | * ''[[Обобщенная двухсерверная задача]]'', | ||
Строка 55: | Строка 54: | ||
* ''[[Системы метрических задач]]'', | * ''[[Системы метрических задач]]'', | ||
* ''[[ | * ''[[Онлайн-алгоритм подкачки и кэширования]]'', | ||
* ''[[Подкачка страниц]]'', | * ''[[Подкачка страниц]]'', | ||
* ''[[Алгоритм рабочей функции для k серверов]]'' | * ''[[Алгоритм рабочей функции для k серверов]]'' | ||
== Литература == | == Литература == |
правок