Distributed minimum spanning tree

From Wikipedia, the free encyclopedia

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(VlogV) time in 1983 by Gallagher et al [1]. Later the solution was improved to O(V) [2] and finally [3] 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 [4] \Omega\left({\frac{\sqrt V}{\log V}}\right).

[edit] 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.

[edit] Applications

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

[edit] References

  1. ^ Robert G. Gallager, Pierre A. Humblet, and P. M. Spira, "A distributed algorithm for minimum-weight spanning trees," ACM TOPLAS,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 Annual 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)", IEEE Symposium on Foundations of Computer Science, 1993.
  4. ^ David Peleg and Vitaly Rubinovich “A near tight lower bound on the time complexity of Distributed Minimum Spanning Tree Construction”, SIAM Journal of Computing, 2000, and IEEE Foundations of Computer Science (FOCS) Symposium, 1999.