|
 
|
[CRV11] The First Fully Polynomial Stabilizing Algorithm for BFS Tree Construction
Conférence Internationale avec comité de lecture : 15th International Conference on Principles of Distributed Systems (OPODIS), December 2011, pp.159-174, Series Lecture Notes in Computer Science, Toulouse, France,
motcle:
Résumé:
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. \emph{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(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 $O(d^2)$ and its step complexity is in $O(n^6)$.
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.
Equipe:
mim
Collaboration:
Laboratoire MIS
BibTeX
| @inproceedings { | |||
| CRV11, | |||
| title | = | "{The First Fully Polynomial Stabilizing Algorithm for BFS Tree Construction}", | |
| author | = | " A. Cournier and S. Rovedakis and V. Villain ", | |
| booktitle | = | "{15th International Conference on Principles of Distributed Systems (OPODIS)}", | |
| year | = | 2011, | |
| edition | = | "Springer", | |
| month | = | "December", | |
| series | = | "Lecture Notes in Computer Science", | |
| pages | = | "159-174", | |
| address | = | "Toulouse, France", | |
| } | |||
