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

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].