Distributed minimum spanning tree: Difference between revisions

Revision as of 19:49, 30 December 2024

Revision as of 19:49, 30 December 2024

Line 2:

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 (computing)|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.

The problem was first suggested and solved in <math>O(V \log V)</math> time in 1983 by Gallager ''et al.'',<ref name="GHS" /> 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 [[David Peleg (scientist)|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><ref>Shay Kutten and [[David Peleg (scientist)|David Peleg]], “Fast Distributed Construction of Smallk-Dominating Sets and Applications,” ''Journal of Algorithms'', Volume 28, Issue 1, July 1998, Pages 40-66.</ref>

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