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. 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.
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. 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 has a minimum-weight edge 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 . The request is handled by 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. A city 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 . As for the wasted messages in the between internal nodes, each node has at most internal edges, or if is a leaf, for a total of wasted internal messages.
Now for the number of stages. By the previously presented property on the cities size, each city of level has , hence the largest reachable rank is . Since cities can merge/be absorbed only once per stage, we have a total of total messages.
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.
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. 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.
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. 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 has a minimum-weight edge 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 . The request is handled by 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. A city 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 . As for the wasted messages in the between internal nodes, each node has at most internal edges, or if is a leaf, for a total of wasted internal messages.
Now for the number of stages. By the previously presented property on the cities size, each city of level has , hence the largest reachable rank is . Since cities can merge/be absorbed only once per stage, we have a total of total messages.
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.