The distributed minimum spanning tree (MST) problem involves the construction of a minimum spanning tree by a distributed algorithm, in a network where nodes communicate by message passing. It is radically different from the classical sequential problem, although the most basic approach resembles Borůvka's algorithm. One important application of this problem is to find a tree that can be used for broadcasting. In particular, if the cost for a message to pass through an edge in a graph is significant, an MST can minimize the total cost for a source process to communicate with all the other processes in the network.
The problem was first suggested and solved in
O(VlogV)
V
O(V)
O(\sqrtVlog*V+D)
\Omega\left({ | \sqrtV |
logV |
+D}\right).
The input graph
G(V,E)
V
E
At the beginning of the algorithm, nodes know only the weights of the links which are connected to them. (It is possible to consider models in which they know more, for example their neighbors' links.)
As the output of the algorithm, every node knows which of its links belong to the minimum spanning tree and which do not.
The message-passing model is one of the most commonly used models in distributed computing. In this model, each process is modeled as a node of a graph. Each communication channel between two processes is an edge of the graph.
Two commonly used algorithms for the classical minimum spanning tree problem are Prim's algorithm and Kruskal's algorithm. However, it is difficult to apply these two algorithms in the distributed message-passing model. The main challenges are:
Due to these difficulties, new techniques were needed for distributed MST algorithms in the message-passing model. Some bear similarities to Borůvka's algorithm for the classical MST problem.
The GHS algorithm of Gallager, Humblet and Spira is one of the best-known algorithms in distributed computing theory. This algorithm constructs an MST in the asynchronous message-passing model.
The GHS algorithm requires several assumptions.
Define a fragment of an MST
T
T
T
T
e
e
These two properties form the basis for proving correctness of the GHS algorithm. In general, the GHS algorithm is a bottom-up algorithm in the sense that it starts by letting each individual node be a fragment, and then joining fragments until a single fragment is left. The above properties imply that the remaining fragment must be an MST.
The GHS algorithm assigns a level to each fragment, which is a non-decreasing integer with initial value 0. Furthermore, each fragment with a non-zero level has an ID, which is the ID of the core edge in the fragment, which is selected when the fragment is constructed. During the execution of the algorithm, each node can classify each of its incident edges into three categories:
In level-0 fragments, each awakened node will do the following:
The edge that is chosen by the two nodes it connects becomes the core edge, and is assigned level 1.
In non-zero-level fragments, a separate algorithm is executed in each level. This algorithm can be separated into three stages: broadcast, convergecast, and change core.
The two nodes adjacent to the core broadcast messages to the rest of the nodes in the fragment. The messages are sent via the branch edge but not via the core. Each broadcast message contains the ID and level of the fragment. At the end of this stage, each node has received the new fragment ID and level.
In this stage, all nodes in the fragment cooperate to find the minimum weight outgoing edge of the fragment. Outgoing edges are edges connecting to other fragments. The messages sent in this stage are in the opposite direction of the broadcast stage. Initialized by all the leaves (the nodes that have only one branch edge), a message is sent through the branch edge. The message contains the minimum weight of the incident outgoing edge it found (or infinity if no such edge was found). The way to find the minimum outgoing edge will be discussed later. For each non-leaf node, given the number of its branch edges as
n
n-1
After the completion of the previous stage, the two nodes connected by the core can inform each other of the best edges they received. Then they can identify the minimum outgoing edge from the entire fragment. A message will be sent from the core to the minimum outgoing edge via a path of branch edges. Finally, a message will be sent out via the chosen outgoing edge to request to combine the two fragments that the edge connects. Depending on the levels of those two fragments, one of two combined operations are performed to form a new fragment; details discussed below.
As discussed above, every node needs to find its minimum weight outgoing incident edge after the receipt of a broadcast message from the core. If node
n
n'
n'
n
FragmentID(n)=FragmentID(n')
n
n'
FragmentID(n) ≠ FragmentID(n')
Level(n)\leqLevel(n')
n
n'
FragmentID(n) ≠ FragmentID(n')
Level(n)>Level(n')
n'
n'
n
Let
F
F'
F
F'
Level(F)=Level(F')
Level(F)+1
Level(F)<Level(F')
F'
Furthermore, when an "Absorb" operation occurs,
F
F'
F'
e
F
F'
n
n'
e
F
F'
n'
F
F'
F
F'
F''
F''
n'
F
F
F
n'
n'
n'
e'
e' ≠ e
weight(e')<weight(e)
n'
e
n
e
n
n'
F
F'
e'
F
As mentioned above, fragments are combined by either "Merge" or "Absorb" operation. The "Absorb" operation does not change the maximum level among all fragments. The "Merge" operation may increase the maximum level by 1. In the worst case, all fragments are combined with "Merge" operations, so the number of fragments decreases by half in each level. Therefore, the maximum number of levels is
O(logV)
V
The GHS algorithm has a nice property that the lowest level fragments will not be blocked, although some operations in the non-lowest level fragments may be blocked. This property implies the algorithm will eventually terminate with a minimum spanning tree.
An
O(logn)
O(D+Llogn)
L