Self-stabilizing extensions for message-passing systems
- 1 August 1990
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 7 (1) , 91-101
- https://doi.org/10.1145/93385.93405
Abstract
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.Keywords
This publication has 5 references indexed in Scilit:
- Token systems that self-stabilizeIEEE Transactions on Computers, 1989
- Uniform self-stabilizing ringsACM Transactions on Programming Languages and Systems, 1989
- The mutual exclusion problemJournal of the ACM, 1986
- Distributed snapshotsACM Transactions on Computer Systems, 1985
- Self-stabilizing systems in spite of distributed controlCommunications of the ACM, 1974