Snap-Stabilization in Message-Passing Systems

Sylvie Delaët 1 Stéphane Devismes 1 Mikhail Nesterenko 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 : In this paper, we tackle the open problem of snap-stabilization in message-passing systems. Snap-stabilization is a nice approach to design protocols that withstand transient faults. Compared to the well-known self-stabilizing approach, snap-stabilization guarantees that the effect of faults is contained immediately after faults cease to occur. Our contribution is twofold: we show that (1) snap-stabilization is impossible for a wide class of problems if we consider networks with finite yet unbounded channel capacity; (2) snap-stabilization becomes possible in the same setting if we assume bounded-capacity channels. We propose three snap-stabilizing protocols working in fully-connected networks. Our work opens exciting new research perspectives, as it enables the snap-stabilizing paradigm to be implemented in actual networks.
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00248465
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 11 février 2008 - 09:50:07
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : mardi 21 septembre 2010 - 15:19:56

Fichiers

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

Identifiants

  • HAL Id : inria-00248465, version 2
  • ARXIV : 0802.1123

Collections

Citation

Sylvie Delaët, Stéphane Devismes, Mikhail Nesterenko, Sébastien Tixeuil. Snap-Stabilization in Message-Passing Systems. [Research Report] RR-6446, INRIA. 2008, pp.29. 〈inria-00248465v2〉

Partager

Métriques

Consultations de la notice

457

Téléchargements de fichiers

184