Self-stabilizing Systems in Spite of Distributed Control
📜 Abstract
In a sparsely connected system with distributed control the local rules of behaviour can guarantee within a bounded number of steps convergence of the system as a whole towards satisfying a global requirement.
✨ Summary
- The paper introduces the concept of self-stabilization: a distributed system must converge to a legitimate state from any initial state, regardless of which enabled local action is selected. It formalizes the model using finite-state machines on a connected graph, local privileges, and a central daemon, then gives three self-stabilizing constructions for token circulation on a ring using K-state, three-state, and four-state machines. (cs.utexas.edu)
- The work became foundational for fault-tolerant distributed computing. It received the 2002 ACM Symposium on Principles of Distributed Computing Influential Paper Award, whose accompanying account identifies it as the source of a research direction in self-stabilization and fault tolerance. (podc.org)
- Subsequent research extended and reexamined Dijkstra’s protocol under different execution and communication models, including unsupportive environments and probabilistically unreliable registers, and later work developed automated synthesis methods capable of producing Dijkstra’s token-ring protocol and related self-stabilizing algorithms. (arxiv.org)