A Simple Distributed Algorithm for the Maintenance of a Spanning Tree

This work is devoted to the problem of spanning tree maintenance in the presence of crash failures in a distributed environment using only local knowledge. Using a pre-constructed spanning tree of a k -connected graph, we present a protocol to maintain a spanning tree in the presence of k –1 consecutive failures. The contribution of this paper is twofold. First, the problem is formalized as an occurrence of the Menger’s theorem in distributed setting. The second result shows an implementation of the protocol which is composed of a set of modules encoded in the asynchronous message passing model. After each failure occurrence, our algorithm maintains a spanning tree in O(N) time using O(M+N) messages and O(Δ) bits per node. Here Δ is the degree, M the number of edges and N the number of nodes of the graph to be maintained. Furthermore, the studied network is semi-anonymous : Only the root needs to be identified.