On the Relationship between Self-Stabilization and Fault Tolerance - Problems and Prospects. Talk held on August 20, 1998 at a Dagstuhl Seminar 98331 on Self-Stabilization at Schloß Dagstuhl, Germany.

Abstract

The paradigm of self-stabilization was introduced as a theoretical concept without a clear relation to fault tolerance. Traditionally, fault tolerance has taken the view that only a subset of nodes may be affected by permanent faults, while in self-stabilization all nodes may experience some form of transient faults. In this talk, I elaborated on the changing perception of self-stabilization as being a paradigm to also deal with permanent faults. Building on the different forms of fault tolerance (masking, non-masking, fail-safe) presented in the talk by Anish Arora, I identified self-stabilization as being an extreme form of non-masking fault tolerance that can also deal with a large class of permanent faults. A first characterization of the faults from this class was given: they must be eventually detectable, not destroy vital redundancy and must be ``stable'' for a sufficiently long period of time. A small example was presented, implications and problems were discussed.

Available as gnuzipped Postscript file.

Felix Gärtner (felix@informatik.tu-darmstadt.de)