Mega-Merger

Short description: Distributed algorithm in graph theory

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 [math]\displaystyle{ C }[/math] has a minimum-weight edge [math]\displaystyle{ e_{merge}(C, C') }[/math] 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 [math]\displaystyle{ e_{merge}(C, C') }[/math]. The request is handled by [math]\displaystyle{ C' }[/math] in the following ways:

1. Friendly merge: [math]\displaystyle{ rank(C) = rank(C') \land e_{merge}(C, C') = e_{merge}(C', C) }[/math]: 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.
2. Absorption: [math]\displaystyle{ rank(C) \lt rank(C') }[/math]: If the requesting city has a lower rank, the city in the receiving end enacts an absorption process: [math]\displaystyle{ C }[/math] is absorbed like in the friendly merge, but loses its name and the resulting city has the rank of [math]\displaystyle{ C' }[/math].
3. Suspension: [math]\displaystyle{ rank(C) = rank(C') \land e_{merge}(C, C') \neq e_{merge}(C', C) \lor rank(C) \gt rank(C') }[/math]: In such cases [math]\displaystyle{ C' }[/math] freezes the request: it waits to either be absorbed by rule 2 or to merge and increase its rank above the one of [math]\displaystyle{ C }[/math] in order to be able to enact rule 1 and absorb [math]\displaystyle{ C }[/math].

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 [math]\displaystyle{ x }[/math] receiving it sends requests to its neighbors, excluding the edges to its child(ren) and parent. The response protocol is as follows:

• [math]\displaystyle{ x.city = y.city }[/math]: clearly the edge is an intra-edge in [math]\displaystyle{ C }[/math]. [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] exchange negative responses.
• [math]\displaystyle{ x.city \neq y.city \land x.rank \lt y.rank }[/math]: [math]\displaystyle{ x }[/math] is asking to a city of higher rank. By rule 2 we can assert that no absorption occurs, and [math]\displaystyle{ y }[/math] indeed belongs to another city.
• [math]\displaystyle{ x.city \neq y.city \land x.rank \gt y.rank }[/math]: in this case [math]\displaystyle{ y }[/math] will delay the answer as by rule 3.

Properties

Mega-Merger holds several properties:

• Monotonic rank: Each city [math]\displaystyle{ C }[/math], mega-city excluded, will eventually rise in rank. By rule 1 [math]\displaystyle{ C }[/math] could friendly merge, raising its rank by [math]\displaystyle{ 1 }[/math]; by rule 2 and 3 [math]\displaystyle{ C }[/math] will have a merge link (by hypothesis [math]\displaystyle{ C }[/math] is not the mega-city) it will either ask a higher-rank city [math]\displaystyle{ C' }[/math], getting absorbed and increasing its rank, or wait until [math]\displaystyle{ C' }[/math] reaches its level and operate a friendly merge.
• [math]\displaystyle{ rank(C) = K \implies |C| \geq 2^k }[/math]: we have a level increase each time a friendly merge is operated. We compute by induction: on the base case, [math]\displaystyle{ rank(C) = 0 }[/math], exactly one village is in [math]\displaystyle{ C }[/math]. On the inductive case, two cities [math]\displaystyle{ C', C'' s.t. rank(C') = rank(C'') = k }[/math] operate a friendly merge, hence [math]\displaystyle{ |C'-C''| = |C'| + |C''| = 2^k + 2^k = 2^{k+1} }[/math] by inductive hypothesis.
• [math]\displaystyle{ \max{rank(C)} \leq \log n }[/math]: by the previous rule cities are built up on an exponential base [math]\displaystyle{ 2 }[/math], hence the inverse [math]\displaystyle{ \log_{2} n }[/math].
• Deadlock prevention: Mega-Merger doesn't incur in any deadlock. As shown by rule 3 a city [math]\displaystyle{ C }[/math] can wait for a lower-rank city to answer on merge link [math]\displaystyle{ e }[/math]: in order to incur in a deadlock such city [math]\displaystyle{ C' }[/math] would have to wait on [math]\displaystyle{ C'' }[/math], and [math]\displaystyle{ C'' }[/math] on [math]\displaystyle{ C''' }[/math], and so on until a cycle is detected on [math]\displaystyle{ C^n }[/math] waiting on [math]\displaystyle{ C }[/math] on a merge link [math]\displaystyle{ e' }[/math]. But by hypothesis [math]\displaystyle{ e }[/math] is the merge-link of [math]\displaystyle{ C }[/math], hence such chain cannot exist. The other deadlock-inducing situation is a request from [math]\displaystyle{ C }[/math] to [math]\displaystyle{ C' }[/math] where [math]\displaystyle{ C' }[/math] has a different merge link than [math]\displaystyle{ C }[/math]. Still, as shown by monotonic rank either [math]\displaystyle{ C' }[/math] will grow its rank to absorb [math]\displaystyle{ C }[/math], or will consume all its merge links to be the only city in the graph with [math]\displaystyle{ C }[/math]. Trivially in such case the two merge links would coincide and [math]\displaystyle{ C' }[/math] would be forced into absorption by rule 2.

Termination

Termination is granted by deadlock prevention and total reliability.

Cost

The cost analysis has two components, the stage-cost and the stage upper-bound. A city [math]\displaystyle{ C }[/math] 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:

1. Broadcast request for merge link to the [math]\displaystyle{ \leq n }[/math] nodes in the tree.
2. Each node forwards an [math]\displaystyle{ outside? }[/math] message to its [math]\displaystyle{ \leq n }[/math] neighbors and waits for their [math]\displaystyle{ \leq n }[/math] answers.
3. The nodes then send the answers back to the city ruler by convergecast for a total of [math]\displaystyle{ \leq n }[/math] messages.
4. The root then decides on a merge link and sends a message to the elected node. Trivially this message will need to travel [math]\displaystyle{ height(Tree) \leq n }[/math] nodes.

These five phases of request, outside discovery, communication and delivery have a total cost of [math]\displaystyle{ n + 2n + n + n \leq 5n }[/math]. As for the wasted messages in the [math]\displaystyle{ outside? }[/math] between internal nodes, each node [math]\displaystyle{ x }[/math] has at most [math]\displaystyle{ deg(x) - 2 }[/math] internal edges, or [math]\displaystyle{ deg(x) - 1 }[/math] if [math]\displaystyle{ x }[/math] is a leaf, for a total of [math]\displaystyle{ 2m - n }[/math] wasted internal messages.

Now for the number of stages. By the previously presented property on the cities size, each city of level [math]\displaystyle{ k }[/math] has [math]\displaystyle{ \geq 2^k }[/math], hence the largest reachable rank is [math]\displaystyle{ log_2{n} }[/math]. Since cities can merge/be absorbed only once per stage, we have a total of [math]\displaystyle{ 2m + n + 5n \log{n} }[/math]total messages.

Correctness

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.