Chandy-Lamport Distributed Snapshot Algorithm

The algorithm operates on the assumption of FIFO, reliable, point-to-point channels between processes in a system modeled as a directed graph. A snapshot is initiated when one or more processes record their own local state and immediately send a special marker message on all outgoing channels, before resuming normal operation. The core invariant being enforced is that the resulting global state is a valid consistent cut — meaning if the snapshot records that a message was received, it must also record that it was sent, but not necessarily vice versa (in-flight messages are captured explicitly, not lost).

Each process follows a simple rule set upon marker arrival: on receiving the first marker on any incoming channel, a process immediately records its own local state, then forwards the marker on all of its outgoing channels before processing any further application messages from that point forward. For any channel from which the marker arrives after the process has already recorded its state, the process logs all application messages received on that channel between its own snapshot and the marker’s arrival as the recorded state of that channel. This is the mechanism that captures messages in transit at the moment of the logical cut — without it, the snapshot would be inconsistent (recording a receive event with no corresponding send in the captured state).

Key properties and edge cases engineers must account for:

• Non-blocking: processes never pause to wait for the snapshot to complete; they interleave marker handling with normal execution, which is why this scales to production systems rather than requiring stop-the-world coordination.
• Termination detection is a separate concern — a coordinator (or diffusion-based completion protocol) must detect when every process has recorded its state and every channel’s marker has been processed, since there’s no global clock to signal ‘snapshot complete.’
• Channel ordering dependency: the algorithm’s correctness collapses if channels are not FIFO; message reordering can produce cuts that violate causal consistency (a receive without its corresponding send).
• Multiple concurrent initiators are supported — if several processes trigger snapshots independently, the algorithm still converges on one consistent global cut, since marker semantics are idempotent per channel.

In modern infrastructure, this algorithm underlies distributed checkpointing mechanisms in stream processing engines — Apache Flink’s asynchronous barrier snapshotting is a direct descendant, using barriers (markers) injected into data streams to align exactly-once state checkpoints across parallel operators without pausing the pipeline. It’s also foundational to deadlock detection in distributed databases and to constructing globally consistent views for distributed garbage collection. The core architectural lesson it encodes — that a ‘global state’ in an asynchronous system is not a single instant but a causally-consistent cut reconstructed from local observations plus channel history — informs how engineers reason about consistency in any system lacking synchronized clocks.