A protocol to maintain a minimum spanning tree in a dynamic topology
Open Access
- 1 August 1988
- proceedings article
- Published by Association for Computing Machinery (ACM)
- Vol. 18 (4) , 330-337
- https://doi.org/10.1145/52324.52357
Abstract
We present a distributed protocol for updating and maintaining a minimum-weight spanning tree (MST) in a network with changing topology. The protocol can respond to multiple link/node failures and recoveries that can occur at arbitrary times. Given that an arbitrary finite number of topological changes occur during a period, the protocol finds the MST corresponding to the latest network, within finite time after the last change. The message complexity of the protocol is O(m|E|+k|V|) when k link recoveries and m link failures occur, where |V| and |E| are the total number of nodes and links, respectively.Keywords
This publication has 8 references indexed in Scilit:
- Tree-Based Broadcasting in Multihop Radio NetworksIEEE Transactions on Computers, 1987
- Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problemsPublished by Association for Computing Machinery (ACM) ,1987
- Reliable broadcast protocols in unreliable networksNetworks, 1986
- A resilient distributed protocol for network synchronizationPublished by Association for Computing Machinery (ACM) ,1986
- Improvements in the time complexity of two message-optimal election algorithmsPublished by Association for Computing Machinery (ACM) ,1985
- A Distributed Algorithm for Minimum-Weight Spanning TreesACM Transactions on Programming Languages and Systems, 1983
- Distributed TerminationACM Transactions on Programming Languages and Systems, 1980
- Reverse path forwarding of broadcast packetsCommunications of the ACM, 1978