Paper Info
Title
The first fully polynomial stabilizing algorithm for BFS tree construction
Abstract
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 recover a correct behavior from an arbitrary global state resulting from transient faults. A fully polynomial algorithm has a round complexity in O(da) and a step complexity in O(nb) 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 O(d2) and its step complexity is in O(n6). To our knowledge, since in general the diameter of a network is much smaller than the number of nodes (log(n) in average instead of n), this algorithm reaches the best compromise of the literature between the complexities in terms of rounds and in terms of steps.
Year
DOI
Venue
2011
10.1007/978-3-642-25873-2_12
OPODIS
Keywords
Field
DocType
breadth first search,bfs tree,correct behavior,network reset,step complexity,bfs tree construction,best compromise,tree construction,arbitrary global state,polynomial algorithm,round complexity,fault tolerance,distributed systems
Minimum degree spanning tree,Distributed minimum spanning tree,Polynomial,Computer science,k-minimum spanning tree,Breadth-first search,K-ary tree,Algorithm,Spanning tree,Distributed computing,Minimum spanning tree
Conference
Volume
ISSN
Citations 
7109
0302-9743
12
PageRank 
References 
Authors
0.55
21
3
Name
Order
Citations
PageRank
Alain Cournier128122.07
Stéphane Rovedakis2120.89
Vincent Villain354445.77