The Distributed Minimum Spanning Tree Problem
Abstract
This article surveys the distributed minimum spanning tree (MST) problem, a central and one of the most studied problems in distributed computing.
In this problem, we are given a network, represented as a weighted graph G = (V; E), and the nodes in the network communicate by message passing via the edges of G with the goal of constructing an MST of G in a distributed fashion, i.e., each node should identify the MST edges incident to itself. This article summarizes the long line of research in designing efficient distributed algorithms and showing lower bounds for the distributed MST problem, including the most recent developments which have focused on algorithms that are simultaneously round- and message-optimal.
In this problem, we are given a network, represented as a weighted graph G = (V; E), and the nodes in the network communicate by message passing via the edges of G with the goal of constructing an MST of G in a distributed fashion, i.e., each node should identify the MST edges incident to itself. This article summarizes the long line of research in designing efficient distributed algorithms and showing lower bounds for the distributed MST problem, including the most recent developments which have focused on algorithms that are simultaneously round- and message-optimal.
Full Text:
PDFRefbacks
- There are currently no refbacks.