Distributed minimum spanning tree: Difference between revisions

Revision as of 23:05, 31 August 2009

Revision as of 06:30, 16 December 2009

Line 1:

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 <math>O(V \log V)</math> time in 1983 by Gallager et. al. ,<ref>[[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.</ref>, where <math>V</math> is the number of vertices in the [[graph theory|graph]]. Later the solution was improved to <math>O(V)</math><ref>[[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.

</ref> and finally<ref>Juan Garay, Shay Kutten and [[BaruchDavid AwerbuchPeleg]]., “A Sub-Linear “OptimalTime Distributed AlgorithmsAlgorithm for Minimum -Weight Spanning Tree,Trees Counting,(Extended Leader Election, and Related ProblemsAbstract),” ''Proceedings of the 19th ACMIEEE [[Symposium on TheoryFoundations of ComputingComputer Science]]'' (STOCFOCS)'', New York City, New York, May 19871993.</ref>

<math>O(\sqrt V \log^* V + D)</math> where ''D'' is the network, or graph diameter. Lower bound on the time complexity of the solution has been eventually shown to be<ref>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.</ref>

</ref> and finally

<ref>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.</ref>

<math>O(\sqrt V \log^* V + D)</math>

where ''D'' is the network, or graph diameter. Lower bound on the time complexity of the solution has been eventually shown to be

<ref>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.</ref>

<math>\Omega\left({\frac{\sqrt V}{\log V}}\right).</math>

== Approximation algorithms ==

An <math>O(\log n)</math>-approximation algorithm was developed by Maleq Khan and Gopal Pandurangan.<ref name="khan"> 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.</ref>. This algorithm runs in <math>O(D+L\log n)</math> time, where <math>L</math> is the local shortest path diameter<ref name=khan/> of the graph.

== Model ==