Mega-merger is a distributed algorithm aimed at solving the election problem in generic connected undirected graph.
[1][2] Mega-Merger was developed by Robert Gray Gallager at MIT in 1983.
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.
Mega-Merger pushes villages to bind together to form cities according to each other's rank and edges.
Mega-Merger builds a minimum spanning tree over connected graphs provided: No further restrictions are necessary.
The algorithm assigns to each village a name and a rank, the former usually unique.
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.
in the following ways: 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
receiving it sends requests to its neighbors, excluding the edges to its child(ren) and parent.
The response protocol is as follows: Mega-Merger holds several properties: Termination is granted by deadlock prevention and total reliability.
The cost analysis has two components, the stage-cost and the stage upper-bound.
enacts a stage by requesting a merge link from its villages and applying one of the above rules according to the desired situation.
We can divide this stage in five steps: These five phases of request, outside discovery, communication and delivery have a total cost of
Mega-Merger creates a minimum spanning tree by merging sub-trees through the minimum cost path, i.e. the merge link.
By definition of minimum spanning tree, a minimum spanning tree is a set of minimum spanning trees connected through minimum-cost paths.
By construction Mega-Merger forwards a request through its merge-link, and that sooner or later that edge is going to be part of the tree by deadlock prevention.