Distributed minimum spanning tree
.
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
. 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.
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 O(V \log V) time in 1983 by Gallager et al., where V is the number of vertices in the graph.
Later, the solution was improved to O(V) and finally O(\sqrt V \log^* V + D) where D is the network, or graph diameter. A lower bound on the time complexity of the solution has been eventually shown to be \Omega\left({\frac{\sqrt V}{\log V}+D}\right).
. 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.
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 O(V \log V) time in 1983 by Gallager et al., where V is the number of vertices in the graph.
Later, the solution was improved to O(V) and finally O(\sqrt V \log^* V + D) where D is the network, or graph diameter. A lower bound on the time complexity of the solution has been eventually shown to be \Omega\left({\frac{\sqrt V}{\log V}+D}\right). \mathit{Fragment}_\mathit{ID}(n) = \mathit{Fragment}_\mathit{ID}(n') . That is, nodes n and n' belong to same fragment, so the edge is not outgoing. \mathit{Fragment}_\mathit{ID}(n) \neq \mathit{Fragment}_\mathit{ID}(n') and \mathit{Level}(n) \leq \mathit{Level}(n') . That is, nodes n and n' belong to the different fragments, so the edge is outgoing. \mathit{Fragment}_\mathit{ID}(n) \neq \mathit{Fragment}_\mathit{ID}(n') and \mathit{Level}(n) > \mathit{Level}(n') . We cannot make any conclusion.
The reason is that 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 . Merge: This operation occurs if both F and F' share a common minimum weight outgoing edge, and \mathit{Level}(F) = \mathit{Level}(F') . The level of the combined fragment will be \mathit{Level}(F) + 1 .
Absorb: This operation occurs if \mathit{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 an 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:
Text derived from https://en.wikipedia.org/w/index.php?oldid=1343866958 under CC BY-SA 4.0; modifications have been made.