Edsger W. Dijkstra
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.
- 1 Scholten, C.S. Private communication.Google Scholar
Index Terms
- Self-stabilizing systems in spite of distributed control
Recommendations
Uniform and Self-Stabilizing Token Rings Allowing Unfair Daemon
A distributed system consists of a set of processes and a set of communication links, each connecting a pair of processes. A distributed system is said to be self-stabilizing if it converges to a correct system state no matter which system state it ...
Self-Stabilizing Mutual Exclusion in the Presence of Faulty Nodes
FTCS '95: Proceedings of the Twenty-Fifth International Symposium on Fault-Tolerant ComputingThis paper presents the RatchetFT distributed fault-tolerant mutual exclusion algorithm for processor rings. RatchetFT is self-stabilizing, in that if mutual exclusion is lost due to any sequence of on-line failures and repairs of processors, mutual ...
Fault-containing self-stabilizing distributed protocols
Self-stabilization is an elegant approach for designing a class of fault-tolerant distributed protocols. A self-stabilizing protocol is guaranteed to eventually converge to a legitimate state after a transient fault. However, even a minor transient ...
Comments