Optimal distributed algorithm for minimum spanning trees revisited
Michalis Faloutsos, Mart L. Molle · 1995
In an earlier paper, Awerbuch presented an innovative distributed algorithm for solving minimum spanning tree (MST) problems that achieved optimal time and message complexity through the introduction of several advanced features. In this paper, we show that there are some cases where his algorithm can create cycles or fail to achieve optimal time complexity. We then show how to modify the algorithm to avoid these problems, and demonstrate both the correctness and optimality of the revised algorithm. 1 Introduction Given an undirected graph G with N nodes and E edges, with weights assigned to each edge, we want to find a spanning tree for which the combined weight of all its edges is minimized, denoted an MST in the sequel. Furthermore, we want to use a distributed algorithm to find that MST by placing a processor at each node and treating each edge as a bidirectional and error-free communication channel, over which the nodes can exchange messages among themselves. We assume that ini...