Snap-Stabilization in Message-Passing Systems

Sylvie Delaët (1) , Stéphane Devismes (1) , Mikhail Nesterenko (2) , Sébastien Tixeuil (3, 4)

1 LRI - Laboratoire de Recherche en Informatique
2 Department of computer science
3 GRAND-LARGE - Global parallel and distributed computing
4 NPA - Networks and Performance Analysis

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.

Mots clés: Distributed systems; Distributed algorithm; Self-stabilization; Snap-Stabilization

Domaines: Calcul parallèle, distribué et partagé [cs.DC]; Réseaux et télécommunications [cs.NI]; Performance et fiabilité [cs.PF]

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⟩