Мега-слияние - Mega-Merger

Мега-слияние является распределенным алгоритмом, направленным на решение задачи выбора в общем связном неориентированном график.^[1]^[2]

Вступление

Mega-Merger был разработан Робертом Греем Галлагером в Массачусетский технологический институт в 1983 г. Применяется распределенная разделяй и властвуй подход, смешанный со стратегией завоевания на основе рангов. Алгоритм обычно представляет собой аналогию села-города. Каждый узел в графе обозначает деревню, а соединяющие их ребра - дороги, а корневое остовное дерево в подграфе - город. Тогда весь график - это мегаполис. Mega-Merger заставляет деревни объединяться и образовывать города в соответствии с рангом и краями друг друга. Затем города образуются путем союзов или завоевания / поглощения.

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

Mega-Merger строит минимальное остовное дерево по связанным графам:

Полная надежность: Сообщение не теряется при передаче.
UI (уникальный инициатор): Один узел запускает протокол.
Двунаправленные каналы связи: Каждый край является двунаправленным, связь может передаваться в обоих направлениях.

Никаких дополнительных ограничений не требуется.

Алгоритм

Алгоритм присваивает каждой деревне имя и звание, первое из которых обычно уникально. Последний указывает количество дружественных слияний, через которые прошел город, и чем он больше, тем более могущественным считается город. Причем каждому ребру присвоен вес: каждое село / город ${ displaystyle C}$ имеет край минимального веса ${ displaystyle e_ {merge} (C, C ')}$ также называемый ссылка слияния, то есть то ребро, обход которого имеет минимальную стоимость.

Алгоритм работает последовательно, пока не будет сформирован мегаполис. Каждый город C вычисляет свою собственную ссылку слияния и отправляет запрос на слияние через ${ displaystyle e_ {merge} (C, C ')}$ . Запрос обрабатывается ${ displaystyle C '}$ следующими способами:

Дружественное слияние: ${ displaystyle rank (C) = rank (C ') land e_ {merge} (C, C') = e_ {merge} (C ', C)}$ : Если города имеют одну и ту же ссылку слияния и имеют одинаковый ранг, дружеское слияние происходит, и два города сливаются в один. Для вновь созданного города выбирается новое имя, выбирается правящая деревня, и путь от предыдущего правителя к узлу в ссылке слияния переориентируется таким образом, что он ведет к новому лидеру. Ранг нового города также повышен на единицу. Обратите внимание, так как это единственный способ, которым два города могут повысить рейтинг друг друга.
Поглощение: ${ displaystyle rank (C)$ : Если у запрашивающего города более низкий ранг, город на принимающей стороне применяет поглощение процесс: ${ displaystyle C}$ поглощается, как при дружеском слиянии, но теряет свое название, и получившийся город имеет ранг ${ displaystyle C '}$ .
Приостановка: ${ textstyle rank (C) = rank (C ') land e_ {merge} (C, C') neq e_ {merge} (C ', C) lor rank (C)> rank (C')}$ : В таких случаях ${ displaystyle C '}$ замораживает запрос: он ждет, пока его не поглотит правило 2 или объединиться и повысить свой рейтинг выше одного из ${ displaystyle C}$ чтобы иметь возможность ввести правило 1 и впитывать ${ displaystyle C}$ .

Внешние сообщения

Ни у одного узла на графике нет списка деревень, принадлежащих их деревням, поэтому каждый раз, когда город хочет искать ребра, выходящие за его пределы, он должен принимать спросить-ответ протокол. Правитель города отправляет широковещательное сообщение через свое связующее дерево, и каждый узел ${ displaystyle x}$ получив его, он отправляет запросы своим соседям, за исключением ребер дочерних (ren) и родительских. Протокол ответа следующий:

${ displaystyle x.city = y.city}$ : очевидно, что край является внутренним краем в ${ displaystyle C}$ . ${ displaystyle x}$ и ${ displaystyle y}$ обмениваться отрицательными отзывами.
${ Displaystyle x.city neq y.city land x.rank$ : ${ displaystyle x}$ просит город более высокого ранга. По правилу 2 мы можем утверждать, что поглощения не происходит, и ${ displaystyle y}$ действительно принадлежит другому городу.
${ Displaystyle x.city neq y.city land x.rank> y.rank}$ : в этом случае ${ displaystyle y}$ задержит ответ как правило 3.

Характеристики

Mega-Merger владеет несколькими объектами:

Монотонный ранг: Каждый город ${ displaystyle C}$ за исключением мегаполисов, со временем повысится в рейтинге. По правилу 1 ${ displaystyle C}$ может слиться по-дружески, подняв свой ранг на ${ displaystyle 1}$ ; по правилу 2 и 3 ${ displaystyle C}$ будет ссылка на слияние (по гипотезе ${ displaystyle C}$ не мегаполис) либо попросит город более высокого ранга ${ displaystyle C '}$ , поглощаясь и повышая свой ранг, или подождите, пока ${ displaystyle C '}$ достигает своего уровня и работает дружеское слияние.
${ displaystyle rank (C) = K подразумевает | C | geq 2 ^ {k}}$ : у нас повышается уровень каждый раз, когда дружеское слияние эксплуатируется. Вычислим по индукции: в базовом случае ${ displaystyle rank (C) = 0}$ , ровно одна деревня находится в ${ displaystyle C}$ . В индуктивном случае два города ${ displaystyle C ', C''s.t.rank (C') = rank (C '') = k}$ управлять дружественным слиянием, следовательно ${ Displaystyle | C'-C '' | = | C '| + | C' '| = 2 ^ {k} + 2 ^ {k} = 2 ^ {k + 1}}$ по индуктивному предположению.
${ Displaystyle макс {ранг (С)} Leq журнал п}$ : по предыдущему правилу города застраиваются экспоненциально ${ displaystyle 2}$ , следовательно, обратный ${ Displaystyle журнал _ {2} п}$ .
Предотвращение тупиковых ситуаций: Mega-Merger не заходит в тупик. Как показывает правило 3 город ${ displaystyle C}$ может подождать, пока город более низкого ранга ответит на ссылку слияния ${ displaystyle e}$ : чтобы завести в тупик такой город ${ displaystyle C '}$ придется подождать ${ displaystyle C ''}$ , и ${ displaystyle C ''}$ на ${ displaystyle C '' '}$ , и так далее, пока цикл не будет обнаружен на ${ displaystyle C ^ {n}}$ ожидание ${ displaystyle C}$ по ссылке слияния ${ displaystyle e '}$ . Но по гипотезе ${ displaystyle e}$ это ссылка слияния ${ displaystyle C}$ , следовательно, такой цепочки не может быть. Другая ситуация, вызывающая тупик, - это запрос от ${ displaystyle C}$ к ${ displaystyle C '}$ куда ${ displaystyle C '}$ имеет другую ссылку слияния, чем ${ displaystyle C}$ . Тем не менее, как показывает монотонный ранг, ${ displaystyle C '}$ повысит свой рейтинг, чтобы поглотить ${ displaystyle C}$ , или будет использовать все свои ссылки слияния, чтобы быть единственным городом на графике с ${ displaystyle C}$ . Тривиально в таком случае две ссылки слияния совпадают и ${ displaystyle C '}$ будут вынуждены быть поглощены правилом 2.

Прекращение

Прекращение действия предоставляется предотвращение тупиковых ситуаций и полная надежность.

Расходы

Анализ затрат состоит из двух компонентов: этапных затрат и верхнего предела этапа. Город ${ displaystyle C}$ запускает этап, запрашивая ссылку слияния из своих деревень и применяя одно из вышеперечисленных правил в соответствии с желаемой ситуацией. Мы можем разделить этот этап на пять шагов:

Трансляция запроса на объединение ссылки на ${ Displaystyle Leq п}$ узлы в дереве.
Каждый узел пересылает ${ displaystyle снаружи?}$ сообщение для своего ${ displaystyle leq n}$ соседей и ждет их ${ Displaystyle Leq п}$ ответы.
Затем узлы отправляют ответы обратно правителю города конвергентный в общей сложности ${ Displaystyle Leq п}$ Сообщения.
Затем корень выбирает ссылку слияния и отправляет сообщение выбранному узлу. Банально это сообщение нужно будет путешествовать ${ displaystyle height (Дерево) leq n}$ узлы.

Общая стоимость этих пяти этапов запроса, внешнего обнаружения, связи и доставки составляет ${ Displaystyle п + 2n + п + п leq 5n}$ . Что касается потерянных сообщений в ${ displaystyle снаружи?}$ между внутренними узлами, каждый узел ${ displaystyle x}$ имеет самое большее ${ displaystyle deg (x) -2}$ внутренние края, или ${ displaystyle deg (x) -1}$ если ${ displaystyle x}$ это лист, всего ${ displaystyle 2m-n}$ потраченные впустую внутренние сообщения.

Теперь о количестве этапов. Согласно ранее представленному свойству по размеру городов, каждый город уровня ${ displaystyle k}$ имеет ${ displaystyle geq 2 ^ {k}}$ , следовательно, наибольший достижимый ранг равен ${ displaystyle log_ {2} {n}}$ . Поскольку города могут объединяться / поглощаться только один раз за этап, у нас есть всего ${ displaystyle 2m + n + 5n log {n}}$ всего сообщений.

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

Mega-Merger создает минимальное остовное дерево путем слияния поддеревьев по пути минимальной стоимости, то есть по ссылке слияния. По определению минимального остовного дерева, минимальное остовное дерево - это набор минимальных остовных деревьев, соединенных путями с минимальной стоимостью. По построению Mega-Merger пересылает запрос через ссылку слияния, и рано или поздно это ребро станет частью дерева предотвращение тупиковых ситуаций.