Алгоритм DC-дерева для k серверов на деревьях: различия между версиями
Перейти к навигации
Перейти к поиску
KVN (обсуждение | вклад) |
KVN (обсуждение | вклад) Нет описания правки |
||
Строка 1: | Строка 1: | ||
== Постановка задачи == | |||
В рамках ''k-серверной задачи'' мы хотим спланировать движение <math>k</math> серверов в метрическом пространстве <math>M</math> в ответ на последовательность <math>\rho = r_{1}, r_{2},...,r_{n}</math> | В рамках ''k-серверной задачи'' мы хотим спланировать движение <math>k</math> серверов в метрическом пространстве <math>M</math> в ответ на последовательность <math>\rho = r_{1}, r_{2},...,r_{n}</math> | ||
Строка 17: | Строка 18: | ||
Попытки доказать k-серверную гипотезу привели к открытию k-конкурентных алгоритмов для некоторых ограниченных классов метрических пространств, включая алгоритм DC-TREE для деревьев [4], представленный в следующем разделе. (См. другие примеры в [1, 2, 3]). Дерево представляет собой метрическое пространство, определяемое как связный ациклический граф, дуги которого рассматриваются как отрезки прямых произвольной положительной длины. Это метрическое пространство включает как вершины деревьев, так и точки на дугах, а расстояния измеряются вдоль (уникальных) кратчайших путей. | Попытки доказать k-серверную гипотезу привели к открытию k-конкурентных алгоритмов для некоторых ограниченных классов метрических пространств, включая алгоритм DC-TREE для деревьев [4], представленный в следующем разделе. (См. другие примеры в [1, 2, 3]). Дерево представляет собой метрическое пространство, определяемое как связный ациклический граф, дуги которого рассматриваются как отрезки прямых произвольной положительной длины. Это метрическое пространство включает как вершины деревьев, так и точки на дугах, а расстояния измеряются вдоль (уникальных) кратчайших путей. | ||
== Основные результаты == | |||
Пусть T – дерево, согласно вышеприведенному определению. Пусть даны текущая конфигурация сервера S = {<math>s_{1}</math>, ..., <math>s_{k}</math>}, где <math>s_{k}</math> обозначает местоположение сервера j, и точка запроса r; алгоритм выполняет перемещение нескольких серверов, один из которых окажется в результате в точке r. Для двух точек x, y T, обозначим через [x; y] уникальный путь из x в у в дереве T. Сервер j называется активным, если не существует другого сервера в [<math>s_{j}</math>, r] – {<math>s_{j}</math>}, и j является сервером с минимальным индексом, расположенным в s<math>_{j}</math> (последнее условие необходимо только для разрыва связей). | Пусть T – дерево, согласно вышеприведенному определению. Пусть даны текущая конфигурация сервера S = {<math>s_{1}</math>, ..., <math>s_{k}</math>}, где <math>s_{k}</math> обозначает местоположение сервера j, и точка запроса r; алгоритм выполняет перемещение нескольких серверов, один из которых окажется в результате в точке r. Для двух точек x, y T, обозначим через [x; y] уникальный путь из x в у в дереве T. Сервер j называется активным, если не существует другого сервера в [<math>s_{j}</math>, r] – {<math>s_{j}</math>}, и j является сервером с минимальным индексом, расположенным в s<math>_{j}</math> (последнее условие необходимо только для разрыва связей). | ||
Строка 27: | Строка 29: | ||
Теорема ([4]) Алгоритм DC-TREE является k-конкурентным на деревьях. | Теорема ([4]) Алгоритм DC-TREE является k-конкурентным на деревьях. | ||
Применение | |||
== Применение == | |||
k-серверная задача представляет собой абстракцию различных задач планирования, включая планирование командных действий при чрезвычайных ситуациях, кэширование в многоуровневых системах памяти и управление движением головки в жестких дисках с двумя головками. Тем не менее, в силу ее абстрактной природы k-серверная задача представляет главным образом теоретический интерес. | k-серверная задача представляет собой абстракцию различных задач планирования, включая планирование командных действий при чрезвычайных ситуациях, кэширование в многоуровневых системах памяти и управление движением головки в жестких дисках с двумя головками. Тем не менее, в силу ее абстрактной природы k-серверная задача представляет главным образом теоретический интерес. | ||
Алгоритм DC-TREE можно применять для других пространств при помощи «вложения» их в деревья. К примеру, униформное метрическое пространство (в котором все расстояния равны 1) может быть представлено звездой с лучами длины ½ и, следовательно, к нему может быть применен алгоритм DC-TREE. Это также сразу приводит к созданию k-конкурентного алгоритма для задачи кэширования, цель которой заключается в управлении двухуровневой системой памяти, состоящей из большой основной памяти и кэша, способного хранить до k элементов памяти. Если элемент находится в кэше, то стоимость доступа к нему составляет 0, в противном случае стоимость извлечения его из основной памяти равна 1. Задачу кэширования можно рассматривать как k-серверную задачу в униформном метрическом пространстве, в которой позиции серверов представляют элементы, хранящиеся в кэше. Эта идея может быть еще больше расширена на задачу взвешенного кэширования [3], представляющую собой обобщение задачи кэширования, в котором различные элементы могут иметь разную стоимость. Фактически, если удастся вложить метрическое пространство M в дерево, искажение которого будет ограничено δ, тогда алгоритм DC-TREE становится δk-конкурентным алгоритмом для M. | Алгоритм DC-TREE можно применять для других пространств при помощи «вложения» их в деревья. К примеру, униформное метрическое пространство (в котором все расстояния равны 1) может быть представлено звездой с лучами длины ½ и, следовательно, к нему может быть применен алгоритм DC-TREE. Это также сразу приводит к созданию k-конкурентного алгоритма для задачи кэширования, цель которой заключается в управлении двухуровневой системой памяти, состоящей из большой основной памяти и кэша, способного хранить до k элементов памяти. Если элемент находится в кэше, то стоимость доступа к нему составляет 0, в противном случае стоимость извлечения его из основной памяти равна 1. Задачу кэширования можно рассматривать как k-серверную задачу в униформном метрическом пространстве, в которой позиции серверов представляют элементы, хранящиеся в кэше. Эта идея может быть еще больше расширена на задачу взвешенного кэширования [3], представляющую собой обобщение задачи кэширования, в котором различные элементы могут иметь разную стоимость. Фактически, если удастся вложить метрическое пространство M в дерево, искажение которого будет ограничено δ, тогда алгоритм DC-TREE становится δk-конкурентным алгоритмом для M. | ||
Открытые вопросы | |||
== Открытые вопросы == | |||
Открытой остается k-серверная гипотеза (состоящая в том, что существует k-конкурентный алгоритм для k серверов в любом метрическом пространстве). Было бы интересно доказать ее для некоторых отдельных случаев – к примеру, для плоскости (как с евклидовой метрикой, так и с манхэттенским расстоянием). k-конкурентный алгоритм для манхэттенской плоскости для k = 2 и k = 3 серверов известен [1], но для k ≥ 4 его не существует. | Открытой остается k-серверная гипотеза (состоящая в том, что существует k-конкурентный алгоритм для k серверов в любом метрическом пространстве). Было бы интересно доказать ее для некоторых отдельных случаев – к примеру, для плоскости (как с евклидовой метрикой, так и с манхэттенским расстоянием). k-конкурентный алгоритм для манхэттенской плоскости для k = 2 и k = 3 серверов известен [1], но для k ≥ 4 его не существует. | ||
Мало что известно об онлайновых рандомизированных алгоритмах для k-серверов. Фактически даже для k = 2 неизвестно, существует ли рандомизированный алгоритм с коэффициентом конкурентоспособности меньше 2. | Мало что известно об онлайновых рандомизированных алгоритмах для k-серверов. Фактически даже для k = 2 неизвестно, существует ли рандомизированный алгоритм с коэффициентом конкурентоспособности меньше 2. | ||
Строка 43: | Строка 49: | ||
► Алгоритм рабочей функции для k серверов | ► Алгоритм рабочей функции для k серверов | ||
== Литература == | |||
1. Bein, W., Chrobak, M., Larmore, L.L.: The 3-server problem in the plane. Theor. Comput. Sci. 287, 387-391 (2002) | 1. Bein, W., Chrobak, M., Larmore, L.L.: The 3-server problem in the plane. Theor. Comput. Sci. 287, 387-391 (2002) |