Распределенное минимальное остовное дерево

Пример MST: минимальное остовное дерево планарного графа. Каждое ребро маркируется своим весом, который здесь примерно пропорционален его длине.

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

Проблема была впервые предложена и решена в $O\; (V\; log\; \; V)\; \{\backslash \; displaystyle\; O\; (V\; \backslash \; log\; V)\}$в 1983 году Галлагером и др., где $V\; \{\backslash \; displaystyle\; V\}$- количество вершин в графе. Позже решение было улучшено до $O\; (V)\; \{\backslash \; displaystyle\; O\; (V)\}$и, наконец, $O\; (V\; log\; \ast \; \; V\; +\; D)\; \{\backslash \; displaystyle\; O\; (\{\backslash \; sqrt\; \{V\}\}\; \backslash \; log\; ^\; \{*\}\; V\; +\; D)\}$где D - это сеть или диаметр графа. В конечном итоге было показано, что нижняя граница временной сложности решения составляет $\Omega \; (V\; log\; \; V\; +\; D).\; \{\backslash \; displaystyle\; \backslash \; Omega\; \backslash \; left\; (\{\{\backslash \; frac\; \{\backslash \; sqrt\; \{V\}\}\; \{\backslash \; log\; V\}\}\; +\; D\}\; \backslash \; right).\}$

• 1 Обзор
• 2 MST в сообщении- модель прохождения
• 3 Алгоритм GHS
  • 3.1 Предварительные условия
  • 3.2 Свойства MST
  • 3.3 Описание алгоритма
    • 3.3.1 Широковещательная передача
    • 3.3.2 Конвергентная передача
    • 3.3.3 Изменение ядра
    • 3.3.4 Как найти исходящий край инцидента с минимальным весом?
    • 3.3.5 Как объединить два фрагмента?
    • 3.3.6 Максимальное количество уровней
  • 3.4 Свойство прогресса
• 4 Алгоритма аппроксимации
• 5 Ссылки

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

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

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

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

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

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

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

Алгоритм GHS Галлагера, Хамблета и Спира - один из самых известных алгоритмов в теории распределенных вычислений. Этот алгоритм может построить MST в асинхронной модели передачи сообщений.

Предварительные условия

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

Свойства MST

Определите фрагмент MST T как поддерево T, то есть связное множество узлов и ребер T. Есть два свойства MST:

1. Для данного фрагмента MST T, пусть e будет исходящим ребром минимального веса этого фрагмента. Затем соединение e и соседнего с ним нефрагментарного узла с фрагментом дает еще один фрагмент MST.
2. Если все ребра связного графа имеют разные веса, то MST графа уникален.

Эти два свойства составляют основу для доказательства правильности алгоритма GHS. В общем, алгоритм GHS - это восходящий алгоритм в том смысле, что он начинается с того, что позволяет каждому отдельному узлу быть фрагментом и соединять фрагменты определенным образом для формирования новых фрагментов. Этот процесс соединения фрагментов повторяется до тех пор, пока не останется только один фрагмент, а свойства 1 и 2 не означают, что полученный фрагмент является MST.

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

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

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

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

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

Край, выбранный обоими узлами, которые он соединяет, становится ядром с уровнем 1.

Для фрагмента ненулевого уровня выполнение алгоритма может быть разделено на три этапа на каждом уровне:

Широковещательная передача

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

Convergecast

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

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

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

Как найти минимальный вес падающей исходящей кромки?

Как обсуждалось выше, каждый узел должен найти свой минимальный вес исходящего инцидентного фронта после получения широковещательного сообщения от ядра. Если узел n принимает широковещательную рассылку, он выберет базовое ребро с минимальным весом и отправит сообщение узлу n ’на другой стороне с идентификатором и уровнем его фрагмента. Затем узел n ’решит, является ли край исходящим, и отправит обратно сообщение, чтобы уведомить узел n о результате. Решение принимается в соответствии со следующим:. Случай 1 : Fragment_ID (n) = Fragment_ID (n ').. Тогда узлы n и n' принадлежат одному и тому же фрагменту (поэтому край не является исходящим).. Случай 2 : Fragment_ID (n)! = Fragment_ID (n ') and Level (n) <= Level(n’).. Тогда узлы n и n' принадлежат разным фрагментам (так край выходит).. Случай 3 : Fragment_ID (n)! = Fragment_ID (n ') and Level (n)>Level (n').. Мы не можем сделать никаких выводов. Причина в том, что два узла могут уже принадлежать одному фрагменту, но узел n ’еще не обнаружил этот факт из-за задержки широковещательного сообщения. В этом случае алгоритм позволяет узлу n ’отложить ответ до тех пор, пока его уровень не станет выше или равным уровню, полученному от узла n.

Как совместить два фрагмента?

Пусть F и F ’- два фрагмента, которые необходимо объединить. Это можно сделать двумя способами:

• Объединить : эта операция выполняется, если и F, и F ’имеют общий исходящий край с минимальным весом, а уровень (F) = Уровень (F’). Уровень объединенного фрагмента будет Level (F) + 1.
• Absorb : Эта операция происходит, если Level (F) < Level(F’). The combined fragment will have the same level as F’.

Кроме того, когда происходит операция «Absorb», F должен находиться на стадии изменения сердечника, пока F 'может находиться в произвольной стадии. Следовательно, операции «поглощения» могут выполняться по-разному в зависимости от состояния F ’. Пусть e будет ребром, с которым F и F ’хотят объединиться, и пусть n и n’ будут двумя узлами, соединенными e в F и F ’соответственно. Необходимо рассмотреть два случая:. Случай 1 : Узел n 'получил широковещательное сообщение, но не отправил конвергентное сообщение обратно в ядро.. В этом случае фрагмент F может просто присоединиться к процессу трансляции F '. В частности, мы представляем F и F ’, уже объединенные, чтобы сформировать новый фрагмент F’ ’, поэтому мы хотим найти минимальный вес исходящего края F’ ’. Для этого узел n 'может инициировать широковещательную рассылку в F для обновления идентификатора фрагмента каждого узла в F и сбора исходящего ребра минимального веса в F.. Случай 2 : Узел n' имеет уже отправил конвергентное сообщение обратно в ядро.. Перед тем, как узел n 'отправил конвергентное сообщение, он должен был выбрать исходящий край с минимальным весом. Как мы обсуждали выше, n ’делает это, выбирая базовое ребро с минимальным весом, отправляя тестовое сообщение на другую сторону выбранного ребра и ожидая ответа. Предположим, что e ’выбрано ребро, мы можем заключить следующее:

1. e’! = E
2. weight (e ’) < weight(e)

Второе утверждение следует, если выполняется первое. Для первого оператора предположим, что n ’выбрал ребро e и отправил тестовое сообщение на n через ребро e. Затем узел n задержит ответ (в соответствии со случаем 3 из «Как найти минимальный вес инцидентной исходящей кромки?»). Тогда невозможно, чтобы n ’уже отправил свое конвергентное сообщение. По пунктам 1 и 2 мы можем заключить, что поглощение F в F 'безопасно, поскольку e ’все еще остается минимальным исходящим фронтом, о котором следует сообщить после поглощения F.

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

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

Progress property

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

An $O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$-приближенный алгоритм был разработан Малек Ханом и Гопалом Пандуранган. Этот алгоритм выполняется за $O\; (D\; +\; L\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (D\; +\; L\; \backslash \; log\; n)\}$времени, где $L\; \{\backslash \; displaystyle\; L\}$- диаметр кратчайшего локального пути графа.

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