Distributed minimum spanning tree: Difference between revisions

Revision as of 05:33, 13 September 2013

Latest revision as of 16:25, 27 August 2025

(19 intermediate revisions by 13 users not shown)

Line 1:

[[Image:Minimum spanning tree.svg|thumb|400px|right|''Example of a MST:'' The minimum spanning tree of a [[planar graph]]. Each edge is labeled with its weight, which here is roughly proportional to its length.]]

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, aan 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>

== Overview ==

The input graph <math>G(V,E)</math> is considered to be a network, where vertices <math>V</math> are independent computing nodes and edges <math>E</math> are communication links. Links are weighted as in the classical problem.

At the beginning of the algorithm, nodes know only the weights of the links which are connected to them. (It is possible to consider models in which they know more, for example their neighbors' links.)

As the output of the algorithm, every node knows which of its links belong to the Minimumminimum Spanningspanning Treetree and which do not.

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

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. The communication channel between two processes is an edge of the graph.

* Both [[Prim's algorithm|Prim’s algorithm]] and [[Kruskal's 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 algorithm|Prim’s algorithm]] and [[Kruskal's 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.

Two commonly used algorithms for the classical minimum spanning tree problem are [[Prim's algorithm|Prim’s algorithm]] and [[Kruskal's 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 algorithm|Prim’s algorithm]] and [[Kruskal's 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 algorithm|Prim’s algorithm]] and [[Kruskal's 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.

== GHS algorithm ==

The GHS algorithm<ref name="GHS" /> of [[Robert G. Gallager|Gallager]], Humblet and Spira is one of the best-known algorithms in distributed computing theory. This algorithm canconstructs construct thean MST in the asynchronous [[Message passing|Messagemessage-passing]] model.

=== Assumptions ===

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 passing|Message-passing]] model.

The GHS algorithm requires several assumptions.

* The input graph is connected and undirected.

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

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

* The algorithm should run on a connected undirected graph.

* Each node initially knows the weight forof each edge incident to that node.

* The graph should have distinct finite weights assigned to each edge. (This assumption can be removed by breaking ties between edge weights in a consistent way.)

* Initially, each node is in aan quiescentinactive state. andEach itnode either spontaneously awakens or is awakened by receipt of any message from another node.

* Each node initially knows the weight for each edge incident to that node.

* Initially, each node is in a quiescent state and it either spontaneously awakens or is awakened by receipt of any message from another node.

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

=== Properties of MSTMSTs ===

Define a fragment of aan MST <math>T</math> to be a sub-tree of <math>T,</math>. thatThat is, a fragment is a connected set of nodes and edges of <math>T</math>. ThereMSTs arehave two important properties ofin MSTsrelation to fragments:<ref name="GHS" />

# Given a fragment of aan MST <math>T</math>, let <math>e</math> be a minimum-weight outgoing edge of the fragment. Then joining <math>e</math> and its adjacent non-fragment node to the fragment yields another fragment of an MST.<ref name="GHS" />

# If all the edges of a connected graph have different weights, then the MST of the graph is unique.<ref name="GHS" />

These two properties form the basis for proving correctness of the GHS algorithm. In general, the GHS algorithm is a bottom-up algorithm in the sense that it starts by letting each individual node be a fragment, and then joining fragments inuntil a certainsingle way to form new fragments. This process of joining fragments repeats until therefragment is only one fragment left. andThe propertyabove 1properties andimply 2 implythat the resultingremaining fragment ismust abe an MST.

Define fragment of a MST T to be a sub-tree of T, that is, a connected set of nodes and edges of T. There are two properties of MSTs:

# Given a fragment of a MST T, let e be a minimum-weight outgoing edge of the fragment. Then joining e and its adjacent non-fragment node to the fragment yields another fragment of an MST.<ref name="GHS" />

# If all the edges of a connected graph have different weights, then the MST of the graph is unique.<ref name="GHS" />

These two properties form the basis for proving correctness of the GHS algorithm. In general, the GHS algorithm is a bottom-up algorithm in the sense that it starts by letting each individual node be a fragment and joining fragments in a certain way to form new fragments. This process of joining fragments repeats until there is only one fragment left and property 1 and 2 imply the resulting fragment is a MST.

=== Description of the algorithm ===

The GHS algorithm assigns a ''level'' to each fragment, which is a non-decreasing [[integer]] with initial value 0. EachFurthermore, each fragment with a non-zero level fragment 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 already been determined to be part of the MST.

* '''Rejected''' edges are those that have already been determined not to be part of the MST.

* '''Basic''' edges are all edges that are neither branch edges nor rejected edges.

ForIn level-0 fragments, each awakened node will do the following:

# Choose its minimum-weight incident edge and marksmark that edge as a branch edge.

# Send a message via the branch edge to notify the node on the other side.

# Wait for a message from the other end of the edge.

The edge that is chosen by boththe two nodes it connects becomes the core withedge, and is assigned level 1.

For aIn non-zero -level fragmentfragments, ana executionseparate ofalgorithm theis executed in each level. This algorithm can be separated into three stages: inbroadcast, eachconvergecast, level:and change core.

==== Broadcast ====

Line 63 ⟶ 60:

==== 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, (letgiven the number of its branch edges beas <math>n)</math>, after receiving <math>n - 1</math> 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).

==== HowFinding to findthe minimum -weight incident outgoing edge? ====

As discussed above, every node needs to find its minimum weight outgoing incident edge after the receipt of a broadcast message from the core. If node <math>n</math> receives a broadcast, it will pick its minimum weight basic edge and send a message to the node n’<math>n'</math> on the other side with its fragment’sfragment's ID and level. Then, node n’<math>n'</math> will decide whether the edge is an outgoing edge and send back a message to notify node <math>n</math> of the result. The decision is made according to the following:<br/>

# <math>\mathit{Fragment}_\mathit{ID}(n) = \mathit{Fragment}_\mathit{ID}(n')</math>. That is, nodes <math>n</math> and <math>n'</math> belong to same fragment, so the edge is not outgoing.

'''Case 1''': Fragment_ID(n) = Fragment_ID(n’).<br/>

# <math>\mathit{Fragment}_\mathit{ID}(n) \neq \mathit{Fragment}_\mathit{ID}(n')</math> and <math>\mathit{Level}(n) \leq \mathit{Level}(n')</math>. That is, nodes <math>n</math> and <math>n'</math> belong to the different fragments, so the edge is outgoing.

Then, node n and n’ belongs to same fragment (so the edge is not outgoing).<br/>

# <math>\mathit{Fragment}_\mathit{ID}(n) \neq \mathit{Fragment}_\mathit{ID}(n')</math> and <math>\mathit{Level}(n) > \mathit{Level}(n')</math>. We cannot make any conclusion. The reason is that the two nodes may belong to the same fragment already, but node n’<math>n'</math> has not discovered this fact yet due to the delay of a broadcast message. In this case, the algorithm lets node n’<math>n'</math> postpone the response until its level becomes higher than or equal to the level it received from node <math>n</math>.

'''Case 2''': Fragment_ID(n) != Fragment_ID(n’) and Level(n) <= Level(n’).<br/>

Then, node n and n’ belongs to the different fragments (so the edge is outgoing).<br/>

'''Case 3''': Fragment_ID(n) != Fragment_ID(n’) and Level(n) > Level(n’).<br/>

We cannot make any conclusion. The reason is the two nodes may belong to the same fragment already but node n’ has not discovered this fact yet due to the delay of a broadcast message. In this case, the algorithm lets node n’ postpone the response until its level becomes higher than or equal to the level it received from node n.

==== How to combineCombining two fragments? ====

Let <math>F</math> and F’<math>F'</math> 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 <math>F</math> and F’<math>F'</math> share a common minimum weight outgoing edge, and <math>\mathit{Level}(F) = \mathit{Level}(F’F')</math>. The level of the combined fragment will be <math>\mathit{Level}(F) + 1</math>.

* '''Absorb''': This operation occurs if <math>\mathit{Level}(F) < \mathit{Level}(F’F')</math>. The combined fragment will have the same level as F’<math>F'</math>.

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

{{numbered list

'''Case 1''': Node n’ has received broadcast message but it has not sent a convergecast message back to the core.<br/>

| 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 F’<math>F'</math>. Specifically, we image <math>F</math> and F’<math>F'</math> have already combined to form a new fragment F’’<math>F''</math>, so we want to find the minimum weight outgoing edge of F’’<math>F''</math>. In order to do that, node n’<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.<br/math>.

| Node <math>n'</math> has already sent a convergecast message back to the core. Before node n’<math>n'</math> sent a convergecast message, it must have picked a minimum weight outgoing edge. As we discussed above, n’<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 e’<math>e'</math> is the chosen edge, we can conclude the following:

'''Case 2''': Node n’ has already sent a convergecast message back to the core.<br/>

# <math>e' \neq e</math>

Before node n’ sent a convergecast message, it must have picked a minimum weight outgoing edge. As we discussed above, n’ 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 e’ is the chosen edge, we can conclude the following:

# <math>\mathit{weight}(e') < \mathit{weight}(e)</math>

# e’ != e

The second statement follows if the first one holds. For the first statement, suppose n’<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 "HowFinding to findthe minimum weight incident outgoing edge?"). Then, it is impossible that n’<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 e’<math>e'</math> is still the minimum outgoing edge to report after <math>F</math> is absorbed.

# weight(e’) < weight(e)

}}

The second statement follows if the first one holds. For the first statement, suppose n’ chose the edge e and sent a test message to n via edge e. Then, node n will delay the response (according to case 3 of "How to find minimum weight incident outgoing edge?"). Then, it is impossible that n’ has already sent its convergecast message. By 1 and 2, we can conclude it is safe to absorb F into F' since e’ is still the minimum outgoing edge to report after F is absorbed.

==== Maximum number of levels ====

As mentioned above, fragments are combined by either "Merge" or "Absorb" operation. The "Absorb" operation doesn'tdoes not change the maximum level among all fragments. The "Merge" operation may increase the maximum level by 1. In the worst case, all fragments are combined with "Merge" operations, so the number of fragments decreases by half in each level. Therefore, the maximum number of levels is <math>O(\log V)</math>, where <math>V</math> is the number of nodes.

=== Progress property ===

ThisThe GHS algorithm has a nice property that the lowest level fragments will not be blocked, although some operations in the non-lowest level fragments may be blocked. This property implies the algorithm will eventually terminate with a minimum spanning tree.

== Approximation algorithms ==

An <math>O(\log n)</math>-approximation algorithm was developed by Maleq Khan and Gopal Pandurangan.<ref name="khanKhan">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"Khan" /> of the graph.

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

<references>

<ref name="GHS">[[Robert G. Gallager]], Pierre A. Humblet, and P. M. Spira, “A"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>

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

<ref name="Lynch">Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.</ref>

</references>