A highly asynchronous minimum spanning tree protocol

In this paper, we present an efficient distributed protocol for constructing a minimum-weight spanning tree (MST). Gallager, Humblet and Spira [5] proposed a protocol for this problem with time and message complexities O(N log N) and O(E+Nlog N) respectively. A protocol with O(N) time complexity was proposed by Awerbuch [1]. We show that the time complexity of the protocol in [5] can also be expressed as O((D+d) log N), where D is the maximum degree of a node and d is a diameter of the MST and therefore this protocol performs better than the protocol in [1] whenever D+d<N/log N. We give a protocol which requires O(min(N, (D+d)log N)) time and O(E+Nlog Nlog N/loglog N) messages. The protocol constructs a minimum spanning tree by growing disjoint subtrees of the MST (which are referred to as fragments). Fragments having the same minimum-weight outgoing edge are combined until a single fragment which spans the entire network remains. The protocols in [5] and [1] enforce a balanced growth of fragments. We relax the requirement of balanced growth and obtain a highly asynchronous protocol. In this protocol, fast growing fragments combine more often and there-fore speed up the execution.