Distributed Snapshots: Determining Global States of Distributed Systems
đź“ś Abstract
This paper presents an algorithm by which a process in a distributed system determines a global state of the system during a computation. Many problems in distributed systems can be cast in terms of the problem of detecting global states. For instance, the global state detection algorithm helps to solve an important class of problems: stable property detection. A stable property is one that persists: once a stable property becomes true it remains true thereafter. Examples of stable properties are “computation has terminated,” “ the system is deadlocked” and “all tokens in a token ring have disappeared.” The stable property detection problem is that of devising algorithms to detect a given stable property. Global state detection can also be used for checkpointing.
✨ Summary
The paper introduces the Chandy–Lamport distributed snapshot algorithm for recording a consistent global state of an asynchronous distributed system without stopping or otherwise altering the underlying computation. Processes record their local states, while marker messages delimit the messages that were in transit on each incoming channel. Under the paper’s assumptions—reliable, FIFO, finite-delay channels—the resulting collection of process and channel states is a meaningful global state. The correctness argument establishes that the recorded state is reachable from the state at which recording began and that the system can proceed from the recorded state to the state at which recording terminates. This property supports detection of stable conditions such as termination and deadlock, as well as checkpointing.
The paper became a foundation for subsequent distributed-snapshot research. Later work developed variants for synchronous communication and repeated snapshots, examined limitations and modifications under different system assumptions, and produced formal machine-checked proofs of the algorithm and its stable-property-detection application. (sciencedirect.com)
The algorithm also influenced industry systems. Apache Flink documents its fault-tolerance mechanism as a variant of Chandy–Lamport snapshotting, using asynchronous barriers to create consistent snapshots of distributed operator state and input positions for checkpoint-based recovery. (nightlies.apache.org)