Content deleted Content added
Kaltenmeyer (talk | contribs) m →Combining two fragments: typo, typo(s) fixed: aformentioned → aforementioned |
Link suggestions feature: 3 links added. |
||
| (10 intermediate revisions by 4 users not shown) | |||
Line 4:
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 31:
* Each edge in the input graph has distinct finite weights. This assumption is not needed if there is a consistent method to break ties between edge weights.
* Each node initially knows the weight of each edge incident to that node.
* Initially, each node is in an inactive state. Each
* Messages can be transmitted independently in both directions on an edge and arrive after an unpredictable but finite delay, without error.
* Each edge delivers messages in [[FIFO (computing and electronics)|FIFO]] order.
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.
Line 77:
Furthermore, when an "Absorb" operation occurs, <math>F</math> must be in the stage of changing the core, while <math>F'</math> can be in an arbitrary stage. Therefore, "Absorb" operations may be done differently depending on the state of <math>F'</math>. Let <math>e</math> be the edge that <math>F</math> and <math>F'</math> want to combine with, and let <math>n</math> and <math>n'</math> be the two nodes connected by <math>e</math> in <math>F</math> and <math>F'</math>, respectively. There are two cases to consider:
{{numbered list
| Node <math>n'</math> has received broadcast message but it has not sent a convergecast message back to the core. In this case, fragment <math>F</math> can simply join the broadcast process of <math>F'</math>. Specifically, we image <math>F</math> and <math>F'</math> have already combined to form a new fragment <math>F''</math>, so we want to find the minimum weight outgoing edge of <math>F''</math>. In order to do that, node <math>n'</math> can initiate a broadcast to <math>F</math> to update the fragment ID of each node in <math>F</math> and collect minimum weight outgoing edge in <math>F</math>.
| Node <math>n'</math> has already sent a convergecast message back to the core. Before node <math>n'</math> sent a convergecast message, it must have picked a minimum weight outgoing edge. As we discussed above, <math>n'</math> does that by choosing its minimum weight basic edge, sending a test message to the other side of the chosen edge, and waiting for the response. Suppose <math>e'</math> is the chosen edge, we can conclude the following:▼
▲Node <math>n'</math> has already sent a convergecast message back to the core. Before node <math>n'</math> sent a convergecast message, it must have picked a minimum weight outgoing edge. As we discussed above, <math>n'</math> does that by choosing its minimum weight basic edge, sending a test message to the other side of the chosen edge, and waiting for the response. Suppose <math>e'</math> is the chosen edge, we can conclude the following:
▲<li><math>e' \neq e</math></li>
▲<li><math>\mathit{weight}(e') < \mathit{weight}(e)</math></li>
The second statement follows if the first one holds. For the first statement, suppose <math>n'</math> chose the edge <math>e</math> and sent a test message to <math>n</math> via edge <math>e</math>. Then, node <math>n</math> will delay the response (according to case 3 of "Finding the minimum weight incident outgoing edge"). Then, it is impossible that <math>n'</math> has already sent its convergecast message. By the aforementioned conclusions 1 and 2, we can conclude it is safe to absorb <math>F</math> into <math>F'</math> since <math>e'</math> is still the minimum outgoing edge to report after <math>F</math> is absorbed.
}}
==== Maximum number of levels ====
| |||