Distributed minimum spanning tree: Difference between revisions

Revision as of 18:48, 19 December 2011

Revision as of 17:48, 8 March 2012

Line 1:

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_Broadcasting (computing)|broadcasting]]. In particular, if the cost for a message to pass through an edge in a graph is significant, a 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_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_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_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}}\right).</math>

Line 16:

== MST in message-passing model ==

The [[Message_passingMessage 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. The 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_algorithms algorithm|Prim’s algorithm]] and [[Kruskal's_algorithms algorithm|Kruskal’s algorithm]]. However, it is difficult to apply these two algorithms in the distributed message-passing model. The main challenges are:

* Both [[Prim's_algorithms algorithm|Prim’s algorithm]] and [[Kruskal's_algorithms algorithm|Kruskal’s algorithm]] require processing one node or vertex at a time, making it difficult to make them run in parallel. (For example, Kruskal's algorithm processes edges in turn, deciding whether to include the edge in the MST based on whether it would form a cycle with all previously chosen edges.)

* Both [[Prim's_algorithms algorithm|Prim’s algorithm]] and [[Kruskal's_algorithms algorithm|Kruskal’s algorithm]] require processes to know the state of the whole graph, which is very difficult to discover in the message-passing model.

Due to these difficulties, new techniques were needed for distributed MST algorithms in the message-passing model. Some bear similarities to [[Borůvka's algorithm]] for the classical MST problem.

Line 26:

== GHS algorithm ==

The GHS algorithm of [[Robert G. Gallager|Gallager]], Humblet and Spira is one of the best-known algorithms in distributed computing theory. This algorithm can construct the MST in asynchronous [[Message_passingMessage passing|Message-passing]] model.

=== Preconditions<ref name="GHS" /> ===

Line 57:

For a non-zero level fragment, an execution of the algorithm can be separated into three stages in each level:

==== Broadcast ====

The two nodes adjacent to the core broadcast messages to the rest of the nodes in the fragment. The messages are sent via the branch edge but not via the core. Each broadcast message contains the ID and level of the fragment. At the end of this stage, each node has received the new fragment ID and level.

==== Convergecast ====

In this stage, all nodes in the fragment cooperate to find the minimum weight outgoing edge of the fragment. Outgoing edges are edges connecting to other fragments. The messages sent in this stage are in the opposite direction of the broadcast stage. Initialized by all the leaves (the nodes that have only one branch edge), a message is sent through the branch edge. The message contains the minimum weight of the incident outgoing edge it found (or infinity if no such edge was found). The way to find the minimum outgoing edge will be discussed later. For each non-leaf node, (let the number of its branch edges be n) after receiving n-1 convergecast messages, it will pick the minimum weight from the messages and compare it to the weights of its incident outgoing edges. The smallest weight will be sent toward the branch it received the broadcast from.

==== Change core ====

After the completion of the previous stage, the two nodes connected by the core can inform each other of the best edges they received. Then they can identify the minimum outgoing edge from the entire fragment. A message will be sent from the core to the minimum outgoing edge via a path of branch edges. Finally, a message will be sent out via the chosen outgoing edge to request to combine the two fragments that the edge connects. Depending on the levels of those two fragments, one of two combined operations are performed to form a new fragment (details discussed below).

Line 76 ⟶ 79:

Let F and F’ be the two fragments that need to be combined. There are two ways to do this:<ref name="GHS" /><ref name="Lynch" />

* '''Merge''': This operation occurs if both F and F’ share a common minimum weight outgoing edge, and Level(F) = Level(F’). The level of the combined fragment will be Level(F) + 1.

* '''Absorb''': This operation occurs if Level(F) < Level(F’). The combined fragment will have the same level as F’.

Furthermore, when an "Absorb" operation occurs, F must be in the stage of changing the core while F’ can be in arbitrary stage. Therefore, "Absorb" operations may be done differently depending on the state of F’. Let e be the edge that F and F’ want to combine with and let n and n’ be the two nodes connected by e in F and F’, respectively. There are two cases to consider:<br/>

Line 95 ⟶ 98:

== 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.

== References ==