Mega-merger is a distributed algorithm aimed at solving the election problem in generic connected undirected graph.
Introduction Mega-Merger was developed by Robert Gray Gallager at MIT in 1983. It applies a distributed divide and conquer approach mixed with a rank-based conquer strategy. The algorithm is usually presented through a village-city analogy. Each node in the graph indicates a village, while the edges that connect them are the roads and a rooted spanning tree in a sub-graph is a city. The whole graph is then a mega-city. Mega-Merger pushes villages to bind together to form cities according to each other's rank and edges. Cities are then formed by alliances or by conquering/absorption.
Pre-requisites Mega-Merger builds a minimum spanning tree over connected graphs provided:
Total reliability: No message is lost in transmission. UI (unique initiator): A single node starts the protocol. Bi-directional communications channels: Each edge is bi-directional, communications can travel in both directions. No further restrictions are necessary.
Algorithm The algorithm assigns to each village a name and a rank, the former usually unique. The latter states the number of friendly mergers that the city has gone through, and the larger it is, the more powerful a city is considered. Moreover, to each edge is assigned a weight: each village/city C {\displaystyle C} has a minimum-weight edge e m e r g e ( C , C ′ ) {\displaystyle e_{merge}(C,C')} also called merge link, that is the edge whose traversal has minimum cost. The algorithm proceeds in consecutive stages until a mega-city is formed. Each city C computes its own merge link and sends a request for merging across e m e r g e ( C , C ′ ) {\displaystyle e_{merge}(C,C')} . The request is handled by C ′ {\displaystyle C'} in the following ways:
Friendly merge: r a n k ( C ) = r a n k ( C ′ ) ∧ e m e r g e ( C , C ′ ) = e m e r g e ( C ′ , C ) {\displaystyle rank(C)=rank(C')\land e_{merge}(C,C')=e_{merge}(C',C)} : If the cities share the same merge link and have same rank, a friendly merge occurs, and the two cities merge into one. A new name is picked for the newly created city, a ruling village is picked and the path from the previous ruler to the node in the merge link is re-oriented such that it leads to the new leader. The new city also has its rank increased by one. Notice as this is the only way two cities can increase each other's rank. Absorption: r a n k ( C ) < r a n k ( C ′ ) {\displaystyle rank(C)<rank(C')} : If the requesting city has a lower rank, the city in the receiving end enacts an absorption process: C {\displaystyle C} is absorbed like in the friendly merge, but loses its name and the resulting city has the rank of C ′ {\displaystyle C'} . Suspension: r a n k ( C ) = r a n k ( C ′ ) ∧ e m e r g e ( C , C ′ ) ≠ e m e r g e ( C ′ , C ) ∨ r a n k ( C ) > r a n k ( C ′ ) {\textstyle rank(C)=rank(C')\land e_{merge}(C,C')\neq e_{merge}(C',C)\lor rank(C)>rank(C')} : In such cases C ′ {\displaystyle C'} freezes the request: it waits to either be absorbed by rule 2 or to merge and increase its rank above the one of C {\displaystyle C} in order to be able to enact rule 1 and absorb C {\displaystyle C} .
Outside messages No nodes in the graph have a list of villages belonging to their village, hence each time a city wants to look for edges leading outside of it, it has to adopt an ask-reply protocol. The city ruler sends a broadcast message through its spanning tree, and each node x {\displaystyle x} receiving it sends requests to its neighbors, excluding the edges to its child(ren) and parent. The response protocol is as follows:
x . c i t y = y . c i t y {\displaystyle x.city=y.city} : clearly the edge is an intra-edge in C {\displaystyle C} . x {\displaystyle x} and y {\displaystyle y} exchange negative responses.
… excerpt ends here. Continue reading the full article.
