The first fully polynomial stabilizing algorithm for BFS tree construction

The construction of a spanning tree is a fundamental task in distributed systems which allows to resolve other tasks (i. e. , routing, mutual exclusion, network reset). In this paper, we are interested in the problem of constructing a Breadth First Search (BFS) tree. Stabilization is a versatile technique which ensures that the system recovers a correct behavior from an arbitrary global state resulting from transient faults. A fully polynomial algorithm has a round complexity in O ( d a ) and a step complexity in O ( n b ) where d and n are the diameter and the number of nodes of the network and a and b are constants. We present the first fully polynomial stabilizing algorithm constructing a BFS tree under a distributed daemon. Moreover, as far as we know, it is also the first fully polynomial stabilizing algorithm for spanning tree construction. Its round complexity is in Θ ( d 2 ) and its step complexity is in O ( n 6 ).

Authors

• Alain Cournier
• Stéphane Rovedakis
• Vincent Villain

Keywords

• Distributed systems
• Fault-tolerance
• Stabilization
• Spanning tree construction