Weak vs. Self vs. Probabilistic Stabilization

Stéphane Devismes 1 Sébastien Tixeuil 2, 3 Masafumi Yamashita 4
2 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 strong property that guarantees that a network always resume correct behavior starting from an arbitrary initial state. Weaker guarantees have later been introduced to cope with impossibility results: probabilistic stabilization only gives probabilistic convergence to a correct behavior. Also, weak stabilization only gives the possibility of convergence. In this paper, we investigate the relative power of weak, self, and probabilistic stabilization, with respect to the set of problems that can be solved. We formally prove that in that sense, weak stabilization is strictly stronger that self-stabilization. Also, we refine previous results on weak stabilization to prove that, for practical schedule instances, a deterministic weak-stabilizing protocol can be turned into a probabilistic self-stabilizing one. This latter result hints at more practical use of weak-stabilization, as such algorthms are easier to design and prove than their (probabilistic) self-stabilizing counterparts.
Liste complète des métadonnées

https://hal.inria.fr/inria-00189952
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 26 novembre 2007 - 10:58:32
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : mardi 21 septembre 2010 - 14:48:15

Fichiers

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

Identifiants

  • HAL Id : inria-00189952, version 2
  • ARXIV : 0711.3672

Collections

Citation

Stéphane Devismes, Sébastien Tixeuil, Masafumi Yamashita. Weak vs. Self vs. Probabilistic Stabilization. [Research Report] RR-6366, INRIA. 2007. 〈inria-00189952v2〉

Partager

Métriques

Consultations de la notice

384

Téléchargements de fichiers

170