Distributed Snapshots and Global State Collection
Stub. Consistent global snapshots and their properties, the Chandy-Lamport and Lai-Yang snapshot algorithms, an elementary broadcast algorithm, termination detection (Dijkstra-Scholten, and on a unidirectional ring), and distributed deadlock detection (resource and communication deadlock).
There’s no global clock to freeze and photograph a distributed system, so a “consistent snapshot” has to be defined causally: a cut such that no recorded event depends on an unrecorded one. Chandy-Lamport captures this with marker messages along a channel-based model; Lai-Yang does it without requiring FIFO channels. The same causal-consistency toolkit then solves two applications: termination detection (deciding a computation has finished with no way to ask every process directly) via the Dijkstra-Scholten credit-based scheme, and distributed deadlock detection, for both resource deadlock (wait-for graphs) and communication deadlock.
Outline (TODO — flesh out each)
- Properties of consistent snapshots
- The Chandy-Lamport algorithm
- The Lai-Yang algorithm
- An elementary algorithm for broadcasting
- Termination detection — the Dijkstra-Scholten algorithm; termination detection on a unidirectional ring
- Distributed deadlock detection — resource deadlock, communication deadlock