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.
Type de document :
Communication dans un congrès
35th IEEE International Conference on Distributed Computing Systems (ICDCS), Jun 2015, Columbus, United States. IEEE, pp.589-598, 2015, 〈10.1109/ICDCS.2015.66〉
Liste complète des métadonnées

Littérature citée [57 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01247340
Contributeur : Pierre Fraigniaud <>
Soumis le : lundi 21 décembre 2015 - 17:15:29
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : samedi 29 avril 2017 - 23:26:33

Fichier

final-ICDCS2015.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

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. IEEE, pp.589-598, 2015, 〈10.1109/ICDCS.2015.66〉. 〈hal-01247340〉

Partager

Métriques

Consultations de la notice

427

Téléchargements de fichiers

68