Distributed minimum spanning tree

The distributed minimum spanning tree 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.

The problem was first suggested and solved in $O(V\log V)$ time in 1983 by Gallager et. al., where $V$ is the number of vertices in the graph. Later the solution was improved to $O(V)$ and finally $O({\sqrt {V}}\log ^{*}V+D)$ where D is the network, or graph diameter. Lower bound on the time complexity of the solution has been eventually shown to be $\Omega \left({\frac {\sqrt {V}}{\log V}}\right).$

Approximation algorithms

An $O(\log n)$-approximation algorithm was developed by Maleq Khan and Gopal Pandurangan. This algorithm runs in $O(D+L\log n)$ time, where $L$ is the local shortest path diameter of the graph.

Model

The input graph $G(V,E)$ is considered to be a network, where vertices $V$ are independent computing nodes and edges $E$ are communication links. Links are weighted as in the classical problem.

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.

Applications

Ethernet switches use a distributed minimum spanning tree algorithm to construct a loop-free topology. See spanning tree protocol.