Chandy-Lamport and the Distributed Snapshot
A distributed snapshot captures a consistent global state without stopping the system, using marker messages to separate events that belong before the snapshot from those that happen after it.
A distributed system has no single memory image to photograph
On one computer, capturing state can mean stopping execution and copying memory. In a distributed system, the state is split across processes and communication channels, and there may be no perfectly synchronized clock telling every participant when “now” occurs. Chandy and Lamport’s 1985 paper framed the problem as determining a meaningful global state while the computation continues.[1] Their algorithm became foundational because it showed that a consistent picture can be constructed from local observations and messages without freezing the entire system.
Global state includes messages in flight
Recording only each process’s local variables is insufficient. A message that was sent before a sender’s snapshot but arrives after a receiver’s snapshot must be represented as part of the channel state.
The algorithm uses markers to define the snapshot boundary
An initiating process records its local state and sends a special marker on each outgoing channel. When another process sees its first marker, it records its own local state and forwards markers on its outgoing channels. For each incoming channel, the receiver records messages that arrive after its local snapshot but before the marker on that channel; those messages are considered in transit.[1] The result is a consistent cut through the distributed execution rather than a set of local states sampled at one physical instant.
FIFO channels make marker ordering meaningful
The original Chandy-Lamport algorithm assumes reliable FIFO communication channels. If a marker follows application messages on a channel, FIFO ordering ensures those earlier messages arrive before the marker. This lets the marker separate pre-snapshot traffic from post-snapshot traffic without timestamping every event. Lamport’s publication record places the snapshot paper in the broader line of work on ordering events in systems without a shared clock.[2] The algorithm exploits message order as evidence about causality.
A snapshot is consistent, not necessarily instantaneous
Different processes record their local states at different real times. Correctness comes from preserving causal relationships, not from pretending that every observation happened simultaneously.
The snapshot can detect stable properties of a computation
Chandy and Lamport emphasized stable properties—conditions that, once true, remain true. Examples include termination and certain forms of deadlock.[1] A consistent global state can be tested for such a property even though no process sees the whole system directly. This turned global-state detection into a reusable distributed primitive. Instead of designing a special monitoring protocol for every condition, system designers could first capture a consistent state and then evaluate properties over it.
Checkpointing connected the theory to fault recovery
Distributed snapshots naturally relate to checkpoints. If processes save mutually consistent states, the system can potentially restart from that cut rather than rolling every participant back independently. Koo and Toueg’s 1987 work addressed coordinated checkpointing and rollback recovery, including how to force a minimal set of additional processes to checkpoint so that recovery remains consistent.[3] The snapshot problem therefore became part of a broader effort to make distributed computations recoverable without producing impossible histories after failures.
Recovery needs a state that could really have occurred
If a checkpoint says a receiver processed a message but the sender’s checkpoint says the message had not yet been sent, restarting from those states creates an inconsistent execution. A consistent cut avoids that contradiction.
Vector time generalized reasoning about causality and global states
Friedemann Mattern’s 1989 work on virtual time used vector clocks to characterize causality and global states in distributed systems.[4] Vector timestamps make it possible to reason more precisely about which events could have influenced one another. This line of research complements marker-based snapshots: both replace unavailable global physical time with structures derived from local events and communication. The broader lesson is that a distributed system can reconstruct enough order for correctness without requiring perfectly synchronized clocks.
Snapshot ideas became part of practical rollback-recovery systems
Later rollback-recovery research classified checkpoint-based protocols into coordinated, uncoordinated and communication-induced approaches and combined them with message logging.[5] Elnozahy and collaborators’ survey shows how global-state reasoning feeds practical recovery design. Modern distributed databases, stream processors and dataflow engines often use coordinated checkpoint mechanisms that differ in implementation details but inherit the same conceptual problem: capture enough state and in-flight work to restart from a consistent point while normal processing continues.
The marker idea survives in new forms
A barrier flowing through a dataflow graph or stream pipeline plays a role similar to a snapshot marker: it establishes a logical boundary that allows local state to be assembled into one recoverable global checkpoint.
Why the distributed snapshot belongs in computing history
The Chandy-Lamport snapshot belongs in computing history because it solved a problem that initially appears paradoxical: record the state of a distributed computation even though the computation has no single clock, no shared memory and no global pause.[1] The solution does not manufacture simultaneity. It captures a causally consistent cut.
That distinction became central to distributed-systems thinking. Global truth is often reconstructed from local observations and communication rather than read from one authoritative location. Checkpointing, monitoring, termination detection and debugging all benefit from the ability to reason about a global state assembled this way.
The algorithm’s elegance also comes from its restraint. It requires only local recording, marker messages and channel-order assumptions, yet it creates a global artifact useful for many higher-level tasks. That is why distributed snapshots became more than one algorithm: they became a way of thinking about how global properties can emerge from decentralized evidence.
Works Cited
- 01
- 02Leslie Lamport — Publications Archive microsoft.com
- 03
- 04Mattern — Virtual Time and Global States of Distributed Systems homes.cs.washington.edu
- 05
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead