Improving the time complexity of message-optimal distributed algorithms for minimum-weight spanning trees

Abstract

A distributed algorithm is presented that constructs the minimum-weight spanning tree of an undirected connected graph with distinct node identities. Initially, each node knows only the weight of each of its adjacent edges. When the algorithm terminates, each node knows which of its adjacent edges are edges of the tree. For a graph with n nodes and e edges, the total number of messages required by this algorithm is at most 5n log n + 2e, where each message contains at most one edge weight plus 3 + log n bits. Although the algorithm presented here has the same message complexity as the previously known algorithm due to R.G. Gallager, P.A. Humblet, and P.M. Spira, the time complexity of the algorithm presented improves from Gallager's O(n log n) to O(n log n) time units, where log k is the number of times the log function must be applied to k to obtain a result less than or equal to one. A worst case of Ω(n log n) is also possible. In addition, when the network is synchronous, the algorithm presented is modified further to solve the same problem with the same message complexity but in O(n) time.