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.

Publication
Proc. of the 17th International Conference on Advanced Computing and Communications (ADCOM 2009)
Avatar
Suman Kundu
Assistant Professor of Computer Science and Engineering

My research interests include social network analysis, network data science, granular computing, soft computing, fuzzy and rough sets.

comments powered by Disqus
Next