Миграция данных: различия между версиями

Рисунок 1. Слева: примеры исходного и целевого расположения данных. Справа: соответствующие множества Si и Di

Определение задачи выглядит следующим образом. Предположим, что имеется N дисков и <math>\Delta \;</math> элементов данных и что заданы исходное и целевое расположения (см. пример на рис. 1а). Для каждого элемента i его диски-источники <math>S_i \;</math> определяются как подмножество дисков, содержащих элемент i в своем исходном расположении. Диски-назначения <math>D_i \;</math> представляют собой подмножество дисков, желающих получить элемент i. Иными словами, диски из <math>D_i \;</math> должны хранить элемент i в целевом расположении, но не в исходном. На рис. 1б представлены соответствующие множества <math>S_i \;</math> и <math>D_i \;</math>. Предполагается, что <math>S_i \ne \empty \;</math> и <math>D_i \ne \enpty \;</math> для каждого элемента i. Миграция данных представляет собой перенос данных таким образом, чтобы все множества <math>D_i \;</math> получили элемент i, изначально находившийся в <math>S_i \;</math>, а задача заключается в минимизации общего времени, необходимого для переносов.

Хуллер и др. [ ] разработали 9,5-аппроксимацию для задачи миграции данных, коэффициент которой был впоследствии улучшен до 6:5 + o(1). Далее мы рассмотрим нижние границы задачи.

1. Максимальная полустепень захода ([}): Пусть f$j – количество элементов данных, которые собирается получить диск j. Иными словами, /}j = jfijj 2 Д }|. Тогда ft = maxj f$j является нижней границей оптимума, поскольку диск может получить только один элемент данных в одном раунде.