Self-Stabilizing Systems
Stub. The theory of self-stabilization (a system that reaches a legal state from *any* starting state), and worked examples: stabilizing mutual exclusion on a ring and on a bidirectional array, stabilizing graph coloring, a stabilizing spanning-tree protocol, distributed reset, and stabilizing clock synchronization.
A self-stabilizing system tolerates any transient fault — however severe, however it corrupted the global state — by guaranteeing that it returns to a legal configuration on its own within finite time, with no external intervention. This is a fundamentally different fault-tolerance contract than the failure-classification approach of the earlier fault-tolerance note: instead of naming and tolerating specific fault types, it tolerates arbitrary state corruption by construction. Covers the theoretical foundations (convergence, closure) and re-derives self-stabilizing versions of problems already solved without this guarantee — mutual exclusion, graph coloring, spanning tree construction, distributed reset, and clock synchronization.
Outline (TODO — flesh out each)
- Theoretical foundations of self-stabilization
- Stabilizing mutual exclusion — on a unidirectional ring, on a bidirectional array
- Stabilizing graph coloring
- Stabilizing spanning tree protocol
- Distributed reset
- Stabilizing clock synchronization