Séminaire REGAL
Snap-stabilization in message passing systems.
Thursday, February 7, 2008Stéphane Devismes (LRI-LIP6)
In this presentation, 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-stabilization approach, snap-stabilization guarantees that the effect of faults is contained immediately after faults cease to occur. Our contribution is twofold: - First, we show that snap-stabilization is impossible for a wide class of problems if we consider networks with finite yet unbounded link capacity. - Second, we show that snap-stabilization becomes possible in the same setting if we assume bounded-capacity links. 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.