|
 
|
[CRV19] The First Fully Polynomial Stabilizing Algorithm for BFS Tree
Revue Internationale avec comité de lecture : Journal Information and Computation, vol. 265, pp. 26-56, 2019, (doi:https://doi.org/10.1016/j.ic.2019.01.005)Mots clés: Distributed systems, Fault-tolerance, Stabilization, Spanning tree construction
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. Stabilization is a versatile technique which ensures that the system recovers a correct behavior from an arbitrary global state resulting from transient faults.
A \emph{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 $\Theta(d^2)$ and its step complexity is in $O(n^6)$.
Collaboration:
Laboratoire MIS
BibTeX
| @article { | |||
| CRV19, | |||
| title | = | "{The First Fully Polynomial Stabilizing Algorithm for BFS Tree}", | |
| author | = | "A. Cournier and S. Rovedakis and V. Villain", | |
| journal | = | "Information and Computation", | |
| year | = | 2019, | |
| volume | = | 265, | |
| pages | = | "26-56", | |
| doi | = | "https://doi.org/10.1016/j.ic.2019.01.005", | |
| } | |||
