Space-Optimal Time-Efficient Silent Self-Stabilizing Constructions of Constrained Spanning Trees - Archive ouverte HAL Access content directly
Conference Papers Year : 2015

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

(1, 2) , (3, 4)
1
2
3
4

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.
Fichier principal
Vignette du fichier
final-ICDCS2015.pdf (339.33 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01247340 , version 1 (21-12-2015)

Identifiers

Cite

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⟩
418 View
165 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More