Communication Efficiency in Self-stabilizing Silent Protocols

Stéphane Devismes 1 Toshimitsu Masuzawa 2 Sébastien Tixeuil 3, 4
3 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : Self-stabilization is a general paradigm to provide forward recovery capabilities to distributed systems and networks. Intuitively, a protocol is self-stabilizing if it is able to recover without external intervention from any catastrophic transient failure. In this paper, our focus is to lower the communication complexity of self-stabilizing protocols \emph{below} the need of checking every neighbor forever. In more details, the contribution of the paper is threefold: (i) We provide new complexity measures for communication efficiency of self-stabilizing protocols, especially in the stabilized phase or when there are no faults, (ii) On the negative side, we show that for non-trivial problems such as coloring, maximal matching, and maximal independent set, it is impossible to get (deterministic or probabilistic) self-stabilizing solutions where every participant communicates with less than every neighbor in the stabilized phase, and (iii) On the positive side, we present protocols for coloring, maximal matching, and maximal independent set such that a fraction of the participants communicates with exactly one neighbor in the stabilized phase.
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00340805
Contributeur : Sébastien Tixeuil <>
Soumis le : samedi 22 novembre 2008 - 13:36:29
Dernière modification le : vendredi 6 juillet 2018 - 10:08:02
Document(s) archivé(s) le : lundi 7 juin 2010 - 20:22:36

Fichiers

RR-6731.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00340805, version 1
  • ARXIV : 0811.3760

Collections

Citation

Stéphane Devismes, Toshimitsu Masuzawa, Sébastien Tixeuil. Communication Efficiency in Self-stabilizing Silent Protocols. [Research Report] RR-6731, INRIA. 2008, pp.33. 〈inria-00340805〉

Partager

Métriques

Consultations de la notice

726

Téléchargements de fichiers

212