An Efficient Algorithm to Reconstruct a Minimum Spanning Tree in an Asynchronous Distributed Systems

Abstract

In a highly dynamic asynchronous distributed network, node failure (or recovery) and link failure (or recovery) triggers topological changes. In many cases, reconstructing the minimum spanning tree, after each such topological change, is very much required. In this paper, we have described a distributed algorithm based on message passing to reconstruct the minimum spanning tree after a link failure. The algorithm assumes that no further topological changes occur during the execution of the algorithm. The proposed algorithm requires significantly fewer numbers of messages to reconstruct the spanning tree in comparison to other existing algorithms.