Распределенное минимальное связующее дерево

Задача распределенного минимального связующего дерева (MST) включает в себя построение минимального связующего дерева с помощью распределенного алгоритма в сети, где узлы взаимодействуют посредством передачи сообщений. Она радикально отличается от классической последовательной задачи, хотя самый базовый подход напоминает алгоритм Борувки . Одним из важных применений этой проблемы является поиск дерева, которое можно использовать для широковещательной передачи . В частности, если стоимость прохождения сообщения через ребро графа значительна, MST может минимизировать общую стоимость взаимодействия исходного процесса со всеми другими процессами в сети.

Впервые задача была предложена и решена в $O(V\log V)$ время в 1983 году Галлагером и др. , ^[1] где $V$ — количество вершин в графе . Позже решение было улучшено до $O(V)$ ^[2] и наконец ^[3]^[4] $O({\sqrt {V}}\log ^{*}V+D)$ где D — сеть или диаметр графа. В конечном итоге было показано, что нижняя граница временной сложности решения равна ^[5] $\Omega \left({{\frac {\sqrt {V}}{\log V}}+D}\right).$

Обзор

Входной граф $G(V,E)$ считается сетью, вершины которой $V$ являются независимыми вычислительными узлами и ребрами $E$ являются связями связи. Ссылки оцениваются так же, как и в классической задаче.

В начале алгоритма узлы знают только веса связанных с ними ссылок. (Можно рассмотреть модели, в которых они знают больше, например ссылки своих соседей.)

На выходе алгоритма каждый узел знает, какие из его звеньев принадлежат минимальному остовному дереву, а какие нет.

MST в модели передачи сообщений

Модель передачи сообщений — одна из наиболее часто используемых моделей в распределенных вычислениях . В этой модели каждый процесс моделируется как узел графа. Каждый канал связи между двумя процессами является ребром графа.

Двумя обычно используемыми алгоритмами для решения классической задачи минимального остовного дерева являются алгоритм Прима и алгоритм Крускала . Однако применить эти два алгоритма в модели распределенной передачи сообщений сложно. Основными проблемами являются:

И алгоритм Прима, и алгоритм Крускала требуют обработки одного узла или вершины за раз, что затрудняет их параллельную работу. Например, алгоритм Краскала обрабатывает ребра по очереди, решая, включать ли ребро в MST, исходя из того, будет ли оно образовывать цикл со всеми ранее выбранными ребрами.
И алгоритм Прима, и алгоритм Краскала требуют, чтобы процессы знали состояние всего графа, что очень сложно обнаружить в модели передачи сообщений.

Из-за этих трудностей потребовались новые методы для распределенных алгоритмов MST в модели передачи сообщений. Некоторые из них имеют сходство с алгоритмом Борувки для классической задачи MST.

Алгоритм СГС

Алгоритм СГС ^[1] Галлагера , Хамблета и Спира — один из самых известных алгоритмов в теории распределенных вычислений. Этот алгоритм создает MST в модели асинхронной передачи сообщений.

Предположения

Алгоритм GHS требует нескольких допущений.

Входной граф связный и неориентированный.
Каждое ребро входного графа имеет различные конечные веса. В этом предположении нет необходимости, если существует последовательный метод разрыва связей между весами ребер.
Каждый узел изначально знает вес каждого ребра, инцидентного этому узлу.
Изначально каждый узел находится в неактивном состоянии. Каждый узел либо спонтанно пробуждается, либо пробуждается при получении любого сообщения от другого узла.
Сообщения могут передаваться независимо в обоих направлениях на грани и прибывать после непредсказуемой, но конечной задержки, без ошибок.
Каждый край доставляет сообщения в порядке FIFO .

Свойства МСТ

Определить фрагмент MST $T$ быть поддеревом $T$ . То есть фрагмент — это связный набор узлов и ребер $T$ . MST имеют два важных свойства по отношению к фрагментам: ^[1]

Учитывая фрагмент MST $T$ , позволять $e$ — выходное ребро фрагмента минимального веса. Затем присоединяюсь $e$ и его соседний с фрагментом узел, не являющийся фрагментом, дает другой фрагмент MST.
Если все ребра связного графа имеют разные веса, то MST графа уникален.

Эти два свойства составляют основу доказательства правильности алгоритма СГС. В общем, алгоритм GHS представляет собой восходящий алгоритм в том смысле, что он начинается с того, что каждый отдельный узел становится фрагментом, а затем объединяется с фрагментами до тех пор, пока не останется один фрагмент. Вышеуказанные свойства подразумевают, что оставшийся фрагмент должен быть MST.

Описание алгоритма

Алгоритм GHS присваивает уровень каждому фрагменту, который представляет собой неубывающее целое число с начальным значением 0. Кроме того, каждый фрагмент с ненулевым уровнем имеет идентификатор , который является идентификатором ребра ядра во фрагменте, который выбирается при построении фрагмента. В ходе выполнения алгоритма каждый узел может классифицировать каждое свое инцидентное ребро на три категории: ^[1]^[6]

Ребра ответвлений — это те, которые были определены как часть MST.
Отклоненные ребра — это те, которые не являются частью MST.
Базовыми ребрами являются все ребра, которые не являются ни ветвями, ни отклоненными ребрами.

Во фрагментах уровня 0 каждый пробуждённый узел будет делать следующее:

Выберите инцидентное ребро с минимальным весом и отметьте это ребро как ребро ветвления.
Отправьте сообщение через край ветки, чтобы уведомить узел на другой стороне.
Дождитесь сообщения с другого конца края.

Ребро, выбранное двумя узлами, которые оно соединяет, становится ребром ядра и получает уровень 1.

Во фрагментах ненулевого уровня на каждом уровне выполняется отдельный алгоритм. Этот алгоритм можно разделить на три этапа: широковещательная передача, конвергентная передача и изменение ядра.

Транслировать

Два узла, смежные с ядром, широковещательно передают сообщения остальным узлам фрагмента. Сообщения отправляются через границу ветки, но не через ядро. Каждое широковещательное сообщение содержит идентификатор и уровень фрагмента. В конце этого этапа каждый узел получил новый идентификатор фрагмента и уровень.

Конвергекаст

На этом этапе все узлы фрагмента взаимодействуют, чтобы найти выходное ребро фрагмента с минимальным весом. Исходящие ребра — это ребра, соединяющиеся с другими фрагментами. Сообщения, отправленные на этом этапе, находятся в направлении, противоположном этапу широковещания. Инициализируемое всеми листьями (узлами, имеющими только одно ребро ветки), сообщение отправляется через ребро ветки. Сообщение содержит минимальный вес инцидентного исходящего ребра, которое оно обнаружило (или бесконечность, если такое ребро не найдено). Способ нахождения минимального исходящего фронта будет обсуждаться позже. Для каждого нелистового узла задано количество ребер его ветвления как $n$ , после получения $n-1$ конвергентных сообщений, он выберет минимальный вес из сообщений и сравнит его с весами его инцидентных исходящих ребер. Наименьший вес будет отправлен в ветку, из которой он получил трансляцию.

Изменить ядро

После завершения предыдущего этапа два узла, соединенные ядром, могут сообщить друг другу о лучших ребрах, которые они получили. Тогда они смогут определить минимальное выходящее ребро из всего фрагмента. Сообщение будет отправлено от ядра к минимальному исходящему ребру по пути ветвей. Наконец, через выбранный исходящий край будет отправлено сообщение с запросом на объединение двух фрагментов, которые соединяет край. В зависимости от уровней этих двух фрагментов для формирования нового фрагмента выполняется одна из двух комбинированных операций; подробности обсуждаются ниже.

Нахождение исходящего ребра минимального веса

Как обсуждалось выше, каждому узлу необходимо найти свой минимальный вес исходящего инцидентного края после получения широковещательного сообщения от ядра. Если узел $n$ получает широковещательную рассылку, он выберет базовое ребро минимального веса и отправит сообщение узлу $n'$ с другой стороны с идентификатором и уровнем фрагмента. Затем узел $n'$ решит, является ли ребро исходящим ребром, и отправит обратно сообщение для уведомления узла $n$ результата. Решение принимается исходя из следующего:

${\mathit {Fragment}}_{\mathit {ID}}(n)={\mathit {Fragment}}_{\mathit {ID}}(n')$ . То есть узлы $n$ и $n'$ принадлежат одному и тому же фрагменту, поэтому ребро не является исходящим.
${\mathit {Fragment}}_{\mathit {ID}}(n)\neq {\mathit {Fragment}}_{\mathit {ID}}(n')$ и ${\mathit {Level}}(n)\leq {\mathit {Level}}(n')$ . То есть узлы $n$ и $n'$ принадлежат разным фрагментам, поэтому ребро является исходящим.
${\mathit {Fragment}}_{\mathit {ID}}(n)\neq {\mathit {Fragment}}_{\mathit {ID}}(n')$ и ${\mathit {Level}}(n)>{\mathit {Level}}(n')$ . Мы не можем сделать никакого вывода. Причина в том, что два узла могут уже принадлежать одному и тому же фрагменту, но узел $n'$ еще не обнаружил этого факта из-за задержки широковещательного сообщения. В этом случае алгоритм позволяет узлу $n'$ отложить ответ до тех пор, пока его уровень не станет выше или равен уровню, полученному от узла $n$ .

Объединение двух фрагментов

Позволять $F$ и $F'$ быть двумя фрагментами, которые необходимо объединить. Есть два способа сделать это: ^[1]^[6]

Слияние : эта операция происходит, если оба $F$ и $F'$ имеют общий исходящий край минимального веса и ${\mathit {Level}}(F)={\mathit {Level}}(F')$ . Уровень объединенного фрагмента будет ${\mathit {Level}}(F)+1$ .
Поглощение : Эта операция происходит, если ${\mathit {Level}}(F)<{\mathit {Level}}(F')$ . Объединенный фрагмент будет иметь тот же уровень, что и $F'$ .

Более того, когда происходит операция «Поглощение», $F$ должен находиться в стадии изменения ядра, при этом $F'$ может находиться в произвольной стадии. Поэтому операции «Поглощение» могут выполняться по-разному в зависимости от состояния $F'$ . Позволять $e$ быть тем краем, который $F$ и $F'$ хотите объединить с, и пусть $n$ и $n'$ быть двумя узлами, соединенными $e$ в $F$ и $F'$ , соответственно. Следует рассмотреть два случая:

Узел $n'$ получил широковещательное сообщение, но не отправил обратно в ядро сообщение конвергентной рассылки. В этом случае фрагмент $F$ можно просто присоединиться к процессу трансляции $F'$ . В частности, мы изображаем $F$ и $F'$ уже объединились, образовав новый фрагмент $F''$ , поэтому мы хотим найти минимальное выходное ребро веса $F''$ . Для этого узел $n'$ может инициировать трансляцию на $F$ обновить идентификатор фрагмента каждого узла в $F$ и собрать минимальное весовое исходящее ребро в $F$ .
Узел $n'$ ${\ displaystyle n '}$ уже отправил конвергентное сообщение обратно в ядро. До узла $n'$ ${\ displaystyle n '}$ отправил конвергентное сообщение, оно должно было выбрать исходящий край минимального веса. Как мы обсуждали выше, $n'$ ${\ displaystyle n '}$ делает это, выбирая базовое ребро с минимальным весом, отправляя тестовое сообщение на другую сторону выбранного ребра и ожидая ответа. Предполагать $e'$ $е'$ – выбранное ребро, можно сделать следующий вывод:
1. $e'\neq e$
2. ${\mathit {weight}}(e')<{\mathit {weight}}(e)$
Второе утверждение следует, если выполнено первое. Для первого утверждения предположим $n'$ выбрал край $e$ и отправил тестовое сообщение на $n$ через край $e$ . Затем узел $n$ задержит ответ (в соответствии со случаем 3 «Определение минимального веса исходящего фронта»). Тогда невозможно, чтобы $n'$ уже отправил свое сообщение о конвергенции. На основании вышеупомянутых выводов 1 и 2 можно сделать вывод, что поглощение безопасно. $F$ в $F'$ с $e'$ по-прежнему является минимальным исходящим фронтом, о котором необходимо сообщить после $F$ поглощается.

Максимальное количество уровней

Как упоминалось выше, фрагменты объединяются операцией «Слияние» или «Поглощение». Операция «Поглощение» не меняет максимальный уровень среди всех фрагментов. Операция «Слияние» может увеличить максимальный уровень на 1. В худшем случае все фрагменты объединяются операциями «Слияние», поэтому количество фрагментов уменьшается вдвое на каждом уровне. Поэтому максимальное количество уровней равно $O(\log V)$ , где $V$ это количество узлов.

Свойство прогресса

У алгоритма GHS есть приятное свойство: фрагменты самого низкого уровня не будут блокироваться, хотя некоторые операции во фрагментах не самого низкого уровня могут быть заблокированы. Это свойство подразумевает, что алгоритм в конечном итоге завершится с минимальным связующим деревом.

Алгоритмы аппроксимации

Ан $O(\log n)$ Алгоритм -аппроксимации был разработан Малеком Ханом и Гопалом Пандуранганом. ^[7] Этот алгоритм работает в $O(D+L\log n)$ время, где $L$ - локальный диаметр кратчайшего пути ^[7] графика.

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Роберт Г. Галлагер , Пьер А. Хамблет и П. М. Спира, «Распределенный алгоритм для связующих деревьев с минимальным весом», Транзакции ACM в языках и системах программирования , том. 5, нет. 1, стр. 66–77, январь 1983 г.
^ Барух Авербух . «Оптимальные распределенные алгоритмы для остовного дерева минимального веса, подсчета, выбора лидера и связанных с ним проблем», Труды 19-го симпозиума ACM по теории вычислений (STOC) , Нью-Йорк, Нью-Йорк, май 1987 г.
^ Хуан Гарай, Шей Каттен и Дэвид Пелег , «Сублинейный распределенный по времени алгоритм для остовных деревьев минимального веса (расширенный тезис)», Труды симпозиума IEEE по основам информатики (FOCS), 1993.
^ Шей Каттен и Дэвид Пелег , «Быстрое распределенное построение множеств и приложений с доминированием Смолка», Журнал алгоритмов , том 28, выпуск 1, июль 1998 г., страницы 40-66.
^ Дэвид Пелег и Виталий Рубинович «Почти точная нижняя граница временной сложности построения распределенного минимального остовного дерева», SIAM Journal on Computing , 2000 г. и Симпозиум IEEE по основам компьютерных наук (FOCS) , 1999 г.
^ Jump up to: ^а ^б Нэнси А. Линч. Распределенные алгоритмы. Морган Кауфманн, 1996 год.
^ Jump up to: ^а ^б Малек Хан и Гопал Пандуранган. «Алгоритм быстрой распределенной аппроксимации для минимальных остовных деревьев», « Распределенные вычисления » , том 20, № 6, стр. 391–402, апрель 2008 г.

[GHS-1] Jump up to: ^а ^б ^с ^д ^и Роберт Г. Галлагер , Пьер А. Хамблет и П. М. Спира, «Распределенный алгоритм для связующих деревьев с минимальным весом», Транзакции ACM в языках и системах программирования , том. 5, нет. 1, стр. 66–77, январь 1983 г.

[2] Барух Авербух . «Оптимальные распределенные алгоритмы для остовного дерева минимального веса, подсчета, выбора лидера и связанных с ним проблем», Труды 19-го симпозиума ACM по теории вычислений (STOC) , Нью-Йорк, Нью-Йорк, май 1987 г.

[3] Хуан Гарай, Шей Каттен и Дэвид Пелег , «Сублинейный распределенный по времени алгоритм для остовных деревьев минимального веса (расширенный тезис)», Труды симпозиума IEEE по основам информатики (FOCS), 1993.

[4] Шей Каттен и Дэвид Пелег , «Быстрое распределенное построение множеств и приложений с доминированием Смолка», Журнал алгоритмов , том 28, выпуск 1, июль 1998 г., страницы 40-66.

[5] Дэвид Пелег и Виталий Рубинович «Почти точная нижняя граница временной сложности построения распределенного минимального остовного дерева», SIAM Journal on Computing , 2000 г. и Симпозиум IEEE по основам компьютерных наук (FOCS) , 1999 г.

[Lynch-6] Jump up to: ^а ^б Нэнси А. Линч. Распределенные алгоритмы. Морган Кауфманн, 1996 год.

[Khan-7] Jump up to: ^а ^б Малек Хан и Гопал Пандуранган. «Алгоритм быстрой распределенной аппроксимации для минимальных остовных деревьев», « Распределенные вычисления » , том 20, № 6, стр. 391–402, апрель 2008 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]