Self-stabilizing systems in spite of distributed control

1974/11/01 by Edsger W. Dijkstra · 11 citations
Computer Science · #Petri Nets in System Modeling #Distributed systems and fault tolerance

paper · pdf · doi:10.1145/361179.361202

openalex publication_date 1974/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

The synchronization task between loosely coupled cyclic sequential processes (as can be distinguished in, for instance, operating systems) can be viewed as keeping the relation “the system is in a legitimate state” invariant. As a result, each individual process step that could possibly cause violation of that relation has to be preceded by a test deciding whether the process in question is allowed to proceed or has to be delayed. The resulting design is readily—and quite systematically—implemented if the different processes can be granted mutually exclusive access to a common store in which “the current system state” is recorded.

Cited by

• Stabilization and Fault-Tolerance in Presence of Unchangeable Environment Actions
• Unique permutation hashing
• Characterizing Metastable Faults and Failures
• Self-Stabilizing Repeated Balls-into-Bins
• Time-optimal self-stabilizing leader election in population protocols
• Local Computation: Lower and Upper Bounds
• Snap-Stabilizing Linear Message Forwarding
• Benefits of Stabilization versus Rollback in Eventually Consistent Key-Value Stores
• A self-stabilizing algorithm for maximal matching in link-register model in O(nΔ³) moves
• 2-Edge-Connectivity and 2-Vertex-Connectivity of an Asynchronous Distributed Network
• Self-Stabilizing Algorithms in the Uniform Port Model
• Edsger W. Dijkstra [wikipedia]