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(Vlog V) time in 1983 by Gallager et. al.,^[1] where V is the number of vertices in the graph. Later the solution was improved to O(V)^[2] and finally^{[3] [4]} $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^[5] $\Omega\left({\frac{\sqrt V}{\log V}}\right).$

Approximation algorithms

An O(log n)-approximation algorithm was developed by Maleq Khan and Gopal Pandurangan.^[6] This algorithm runs in O(D + Llog n) time, where L is the local shortest path diameter^[6] 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.

References

1. ^ Robert G. Gallager, Pierre A. Humblet, and P. M. Spira, “A distributed algorithm for minimum-weight spanning trees,” ACM Transactions on Programming Languages and Systems, vol. 5, no. 1, pp. 66–77, January 1983.
2. ^ Baruch Awerbuch. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” Proceedings of the 19th ACM Symposium on Theory of Computing (STOC), New York City, New York, May 1987.
3. ^ Juan Garay, Shay Kutten and David Peleg, “A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract),” Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), 1993.
4. ^ Shay Kutten and David Peleg, “Fast Distributed Construction of Smallk-Dominating Sets and Applications,” Journal of Algorithms, Volume 28, Issue 1, July 1998, Pages 40-66.
5. ^ David Peleg and Vitaly Rubinovich “A near tight lower bound on the time complexity of Distributed Minimum Spanning Tree Construction,“ SIAM Journal on Computing, 2000, and IEEE Symposium on Foundations of Computer Science (FOCS), 1999.
6. ^ ^{a b} Maleq Khan and Gopal Pandurangan. “A Fast Distributed Approximation Algorithm for Minimum Spanning Trees,” Distributed Computing, vol. 20, no. 6, pp. 391–402, Apr. 2008.