Мега-Слияние

Мега-слияние — это распределенный алгоритм, направленный на решение задачи выборов в обобщенном связном неориентированном графе .

Введение

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

Прекращение действия

Завершение обеспечивается предотвращением взаимоблокировок и полной надежностью .

Расходы

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

1. Трансляция запроса на ссылку на слияние в $\leq n$ узлы в дереве.
2. Каждый узел пересылает $outside?$ сообщение своему $\leq n$ соседей и ждет своих $\leq n$ ответы.
3. Затем узлы отправляют ответы обратно правителю города посредством конвергентной передачи на общую сумму $\leq n$ сообщения.
4. Затем корень выбирает ссылку слияния и отправляет сообщение выбранному узлу. Тривиально этому сообщению придется путешествовать $height(Tree)\leq n$ узлы.

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

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

Корректность

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