Chandy-Lamport Distributed Snapshot Algorithm: Mechanics and Stream Processing
A technical evaluation of the Chandy-Lamport distributed snapshotting algorithm, examining FIFO channel recording, marker propagation, and Apache Flink checkpoints.
Publication & corrections: infostoa · Editorial standards
Individual author and specialist reviewer information is not provided for this article.
Recording a global state while computation continues
The Chandy–Lamport algorithm records each process’s local state together with messages still in communication channels, producing a meaningful global state while the computation continues. It does not save every node at one synchronized wall-clock instant. The result may not match any single instant that occurred during execution, yet it preserves the causal relationships needed for a consistent cut.
The illustration is a visual analogy of processes, markers, and message directions; the event ordering is explained in the example below.
Marker rules and channel state
The original paper assumes reliable FIFO channels whose messages are delivered in finite time. A process that initiates a snapshot records its local state, then sends a marker on each outgoing channel. A process receiving its first marker records its own state, records the marker’s incoming channel as empty, and sends markers on its outgoing channels. For an input channel whose marker arrives later, it records application messages received after its local snapshot and before that marker. This channel record accounts for messages whose send and receive events fall on opposite sides of the recorded process states.
A possible event order: recording a message on A→B
Consider channels A→B, C→A, and C→B, with all three processes participating in one snapshot. First A sends application message m to B. C records its local state and sends markers to A and B. A receives C’s marker, records its local state, and sends a marker on A→B. That marker must precede later application messages on that channel, though A may send messages after it. At B, C’s marker arrives first, so B records its local state. B then receives m on A→B before A’s marker. Because A sent m before its marker and the channel is FIFO, m arrives first and is recorded in the A→B channel state, not B’s local state.
For the contrasting order, A sends m and then initiates a snapshot. If B receives m before A’s marker, and that marker is B’s first, B’s local state already includes the receive and the recorded A→B channel is empty. The first ordering needs a third process C so its marker can be B’s first marker on another input channel. These are explanatory event traces under the paper’s reliable-FIFO assumption, not an execution log.
How this relates to an engine checkpoint
Apache Flink 1.19 describes checkpoint barriers and operator snapshots that combine application state with stream positions, including aligned and unaligned handling across multiple inputs. Those are details of that release’s implementation, not claims made by the original paper. Restoring internal state alone does not guarantee that effects in an external system will not be duplicated. Check the source, operators, sink, connector, and recovery configuration before describing a pipeline as exactly-once.