Lesson plan

Distributed minimum spanning tree

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

Back to article

Article summary

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

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.