Self-stabilizing Systems in Spite of Distributed Control

Self-stabilizing Systems in Spite of Distributed Control

November 1974 | Edsger W. Dijkstra
The article discusses the concept of self-stabilizing systems in distributed control, focusing on the synchronization of loosely coupled cyclic sequential processes. The author, Edsger W. Dijkstra, highlights the challenge of maintaining a "legitimate state" in such systems, especially when processes have limited communication capabilities and must operate independently based on their local information. Dijkstra introduces the idea of a central daemon that can select privileges for machines to influence their state transitions, ensuring the system returns to a legitimate state after a finite number of moves. He presents three solutions for self-stabilizing systems: one using K-state machines, another using four-state machines, and a third using three-state machines. Each solution is designed to ensure that the system converges to a legitimate state regardless of the initial state or the privileges selected. The article concludes with acknowledgments to C.S. Scholten, C.A.R. Hoare, and M. Woodger for their contributions and helpful comments.The article discusses the concept of self-stabilizing systems in distributed control, focusing on the synchronization of loosely coupled cyclic sequential processes. The author, Edsger W. Dijkstra, highlights the challenge of maintaining a "legitimate state" in such systems, especially when processes have limited communication capabilities and must operate independently based on their local information. Dijkstra introduces the idea of a central daemon that can select privileges for machines to influence their state transitions, ensuring the system returns to a legitimate state after a finite number of moves. He presents three solutions for self-stabilizing systems: one using K-state machines, another using four-state machines, and a third using three-state machines. Each solution is designed to ensure that the system converges to a legitimate state regardless of the initial state or the privileges selected. The article concludes with acknowledgments to C.S. Scholten, C.A.R. Hoare, and M. Woodger for their contributions and helpful comments.
Reach us at info@study.space
Understanding Self-stabilizing systems in spite of distributed control