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

Для каждого элемента i положим <math>\gamma_i = | D_i | \; mod \; k</math>. Необходимо вычислить ''вторичного представителя'' <math>r_i \; </math> в <math>D_i \;</math> для элементов с <math>\gamma_i \ne 0 \;</math>. Диск j может быть вторичным представителем <math>r_i \;</math> для нескольких элементов, если <math>\sum_{i \in I_j} \gamma_i \le 2 \beta + 1 \;</math>, где <math>I_j \;</math> – множество элементов, для которых j является вторичным представителем. Это можно сделать при помощи алгоритма Шмойса-Тардош [17] для обобщенной задачи о назначениях.

2. '''Миграция в <math>r_i \;</math>:''' элемент i отправляется из первичного источника <math>s_i \;</math> в <math>r_i \;</math>. Эту миграцию можно выполнить за <math>1,5 \alpha \;</math> раундов при помощи раскраски ребер [16].

3. '''Миграция на оставшиеся диски:''' Теперь можно создать граф переноса из представителей на оставшиеся диски следующим образом. Для каждого элемента i добавьте ориентированные ребра от дисков в <math>R_i \;</math> к <math>(\beta - 1) \lfloor \frac{|D_i|}{\beta} \rfloor \;</math> дисков в <math>D_i \backslash R_i \;</math>, такие, что полустепень выхода каждой вершины в <math>R_i \;</math> не превышает <math>\beta - 1 \;</math>, а полустепень входа каждой вершины в <math>D_i \backslash \R_i \;</math> из <math>R_i \;</math> равна 1. Также добавляется ориентированное ребро от вторичного представителя <math>r_i \;</math> элемента i к оставшимся дискам в <math>D_i \;</math>, не имеющим входящих ребер из <math>R_i \;</math>. Было показано, что максимальная степень графа переносов не превышает <math>4 \beta - 5 \;</math>, а кратность равна <math>\beta + 2 \;</math>. Следовательно, миграцию из графа переносов можно выполнить за <math>5 \beta - 3 \;</math> раундов при помощи алгоритма раскраски ребер мультиграфа [18].