## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 151-161 |

Number of pages | 11 |

Journal | Distributed Computing |

Volume | 8 |

Issue number | 3 |

DOIs | |

State | Published - Mar 1 1995 |

Externally published | Yes |

## Keywords

- 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