Distributed minimum spanning tree

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.

A lower bound on the time complexity of the solution has been eventually shown to be[5]

At the beginning of the algorithm, nodes know only the weights of the links which are connected to them.

As the output of the algorithm, every node knows which of its links belong to the minimum spanning tree and which do not.

Each communication channel between two processes is an edge of the graph.

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.

This algorithm constructs an MST in the asynchronous message-passing model.

The GHS algorithm assigns a level to each fragment, which is a non-decreasing integer with initial value 0.

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.

At the end of this stage, each node has received the new fragment ID and level.

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

The smallest weight will be sent toward the branch it received the broadcast from.

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.

As discussed above, every node needs to find its minimum weight outgoing incident edge after the receipt of a broadcast message from the core.

receives a broadcast, it will pick its minimum weight basic edge and send a message to the node

Therefore, "Absorb" operations may be done differently depending on the state of

There are two cases to consider: 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 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.

-approximation algorithm was developed by Maleq Khan and Gopal Pandurangan.

is the local shortest path diameter[7] of the graph.