Self-stabilizing extensions for message-passing systems
Shmuel M. Katz, Kenneth J. Perry · 1990
Self-stabilization is an abstraction of fault tolerance for transient malfunctions.Intuitively, a self-stabilizing program resumes normal behavior even if execution begins in an illegal initial state.In this paper, we explore the possibility of extending an arbitrary program into a self-stabilizing one.Our contributions are: (1) a formal definition of the concept of a program being a self-stabilizing extension of a non-stabilizing program; (2) a characterization of what properties may hold in such extensions; (3) a demonstration of the possibility of mechanically creating such extensions.The computational model used is that of an asynchronous distributed message-passing system whose communication topology is an arbitrary graph.We contrast the difficulties of self-stabilization in this model with those of the more common shared-memory models.