A highly asynchronous minimum spanning tree protocol

Gurdip Singh, Arthur J. Bernstein

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)151-161
Number of pages11
JournalDistributed Computing
Issue number3
StatePublished - Mar 1995
Externally publishedYes


  • Distributed algorithms
  • Graph theory
  • Minimum spanning tree
  • Synchronization
  • Time complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computational Theory and Mathematics


Dive into the research topics of 'A highly asynchronous minimum spanning tree protocol'. Together they form a unique fingerprint.

Cite this