Space-Optimal Time-Efficient Silent Self-Stabilizing Constructions of Constrained Spanning Trees

Lélia Blin 1, 2 Pierre Fraigniaud 3, 4
2 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
4 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : Self-stabilizing algorithms are distributed algorithms supporting transient failures. Starting from any configuration, they allow the system to detect whether the actual configuration is legal, and, if not, they allow the system to eventually reach a legal configuration. In the context of network computing, it is known that, for every task, there is a self-stabilizing algorithm solving that task, with optimal space-complexity, but converging in an exponential number of rounds. On the other hand, it is also known that, for every task, there is a self-stabilizing algorithm solving that task in a linear number of rounds, but with large space-complexity. It is however not known whether for every task there exists a self-stabilizing algorithm that is simultaneously space-efficient and time-efficient. In this paper, we make a first attempt for answering the question of whether such an efficient algorithm exists for every task, by focussing on constrained spanning tree construction tasks. We present a general roadmap for the design of silent space-optimal self-stabilizing algorithms solving such tasks, converging in polynomially many rounds under the unfair scheduler. By applying our roadmap to the task of constructing minimum-weight spanning tree (MST), and to the task of constructing minimum-degree spanning tree (MDST), we provide algorithms that outperform previously known algorithms designed and optimized specifically for solving each of these two tasks.
Complete list of metadatas

Cited literature [57 references]  Display  Hide  Download

https://hal.inria.fr/hal-01247340
Contributor : Pierre Fraigniaud <>
Submitted on : Monday, December 21, 2015 - 5:15:29 PM
Last modification on : Tuesday, May 14, 2019 - 11:02:10 AM
Long-term archiving on : Saturday, April 29, 2017 - 11:26:33 PM

File

final-ICDCS2015.pdf
Files produced by the author(s)

Identifiers

Citation

Lélia Blin, Pierre Fraigniaud. Space-Optimal Time-Efficient Silent Self-Stabilizing Constructions of Constrained Spanning Trees. 35th IEEE International Conference on Distributed Computing Systems (ICDCS), Jun 2015, Columbus, United States. pp.589-598, ⟨10.1109/ICDCS.2015.66⟩. ⟨hal-01247340⟩

Share

Metrics

Record views

683

Files downloads

230