Content deleted Content added
No edit summary Tags: Reverted Mobile edit Mobile web edit |
Link suggestions feature: 3 links added. |
||
| (3 intermediate revisions by 2 users not shown) | |||
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>
Line 15:
== MST in message-passing model ==
The [[Message passing|message-passing]] model is one of the most commonly used models in [[distributed computing]]. In this model, each process is modeled as a node of a graph. Each [[communication channel]] between two processes is an edge of the graph.
Two commonly used algorithms for the classical minimum spanning tree problem are [[Prim's algorithm]] and [[Kruskal's algorithm]]. However, it is difficult to apply these two algorithms in the distributed message-passing model. The main challenges are:
Line 43:
=== Description of the algorithm ===
The GHS algorithm assigns a ''level'' to each fragment, which is a non-decreasing [[integer]] with initial value 0. Furthermore, each fragment with a non-zero level has an ''ID'', which is the ID of the core edge in the fragment, which is selected when the fragment is constructed. During the execution of the algorithm, each node can classify each of its incident edges into three categories:<ref name="GHS" /><ref name="Lynch" />
* '''Branch''' edges are those that have been determined to be part of the MST.
* '''Rejected''' edges are those that have been determined not to be part of the MST.
| |||