Distributed minimum spanning tree: Difference between revisions

Revision as of 19:49, 30 December 2024

Revision as of 19:49, 30 December 2024

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