← Wiki Index / Computation & Algorithms / Chandy–Lamport Distributed Snapshot
💻 Computation & Algorithms

Chandy–Lamport Distributed Snapshot

The Chandy–Lamport distributed snapshot algorithm captures a consistent global state of an asynchronous distributed system without halting ongoing computations or synchronizing physical clocks.

The Chandy–Lamport distributed snapshot algorithm is a fundamental distributed algorithm formulated in 1985 by computer scientists K. Mani Chandy and Leslie Lamport to record a consistent global state (a snapshot) of an asynchronous distributed system during ongoing computation. In distributed systems lacking a shared physical clock or shared memory, determining global properties—such as detecting process deadlocks, identifying distributed termination, or establishing valid checkpoint restart points for fault tolerance—is notoriously difficult because independent processes communicate primarily via message-passing channels with variable, unpredictable transmission latencies.

The Chandy–Lamport protocol solves this problem without freezing system execution or halting underlying application transactions. By interleaving special control messages called markers with regular application messages along First-In, First-Out (FIFO) communication channels, the algorithm ensures that the recorded global state forms a consistent cut across space and time.

Chandy-Lamport Marker Propagation Protocol
Process P Process Q
[Local State Recorded] [Local State Running]
│ │
│─── Marker Message (M) ──────────────────────►│
│ Sent along Channel C(P->Q) │
│ │ Marker Arrives:
│ │ 1. Record Local State
│ │ 2. Set Channel C(P->Q) State = Empty
│ │ 3. Send Markers along all Outgoing Channels
│ │ 4. Record Incoming Messages on other channels
│ │ until their markers arrive
▼ ▼
All Channels Flushed by Markers -> Complete Global Snapshot Assembled

System Model and Core Assumptions

The algorithm operates within a standard asynchronous distributed computing model governed by well-defined topological and network ensures.

The distributed system consists of a finite graph of processes interconnected by unidirectional communication channels. Processes communicate only by sending and receiving discrete messages, with processing steps and message propagation delays being finite but arbitrary.

Prerequisites of the Chandy-Lamport Protocol:
1. Strongly Connected Topology: Every process can reach every other process via directed channel paths.
2. FIFO Message Delivery: Messages transmitted along any channel arrive in the precise order they were sent.
3. Reliable Channels: Communication channels do not corrupt, duplicate, or drop transmitted messages.
4. Non-Interfering Execution: Underlying application processing continues uninterrupted during snapshotting.

If communication channels are non-FIFO, the protocol cannot guarantee consistency without additional sequence-number tracking or vector clock mechanisms, making FIFO ordering a foundational structural assumption.

Consistent Cuts and Global State Definitions

The theoretical correctness of the algorithm is rooted in the concept of a consistent cut, formalized by Lamport's happens-before relation (denoted by the causal arrow →).

A global state S is defined as the union of the local states of all individual processes plus the states of all communication channels. A recorded global state is defined as consistent if and only if, for every message m in the system:

Causal Consistency Condition:
If message m is received by process Q prior to Q recording its local state,
then message m must have been sent by process P prior to P recording its local state.

In terms of spacetime diagrams, a consistent cut represents a dividing line across all process worldlines such that no causal event in the future of the cut influences an event in the past of the cut. An inconsistent snapshot would capture "orphan messages"—messages received in the recorded process state whose corresponding transmission event does not exist in the sender's recorded state, violating causality.

Algorithmic Execution: The Marker Rule

The protocol can be initiated concurrently by one or more processes without prior coordination. The entire algorithm is defined by two simple, elegant operational rules: the Marker-Sending Rule and the Marker-Receiving Rule.

Algorithmic Rules of the Chandy-Lamport Protocol:
1. Marker-Sending Rule (for process P):
- Process P records its own local internal state.
- For each outgoing channel C(P->k), P transmits a marker message M
before sending any further application messages along C(P->k).
2. Marker-Receiving Rule (for process Q receiving marker M along channel C(P->Q)):
- If Q has not yet recorded its local state:
* Q promptly records its own local internal state.
* Q marks the state of channel C(P->Q) as empty.
* Q follows the Marker-Sending Rule to send markers along all its outgoing channels.
- If Q has already recorded its local state:
* Q records the state of channel C(P->Q) as the sequence of all messages
received along C(P->Q) between when Q recorded its state and when marker M arrived.

Because channels follow FIFO ordering, the arrival of marker M along channel C(P→Q) acts as a definitive temporal separator: any application message sent by P before P sent the marker arrives at Q before the marker, while any message sent by P after the marker arrives at Q after the marker.

Algorithmic Termination and Snapshot Assembly

The snapshot protocol terminates locally at process Q once Q has received a marker along every one of its incoming channels.

Once all processes have terminated the protocol locally, the distributed snapshot is complete. The global state consists of the set of all recorded local process states alongside the recorded message queues representing messages that were in transit along channels at the moment the snapshot cut crossed those channels. These local state records can then be gathered at a designated coordinator node via distributed reduction or spanning tree aggregation to assemble the composite global picture.

Meaning of the Recorded State

A fundamental property of the Chandy-Lamport snapshot is that the recorded global state may not have occurred at any single instant of physical real time.

Because communication delays are asynchronous, process P may record its state hours before process Q records its state. However, the recorded state is guaranteed to be causally consistent: it represents a valid global state that the distributed system could have passed through along a valid serialization of events. If a stable property (such as deadlock or termination) holds in the recorded state, that property holds in the actual system at the moment the snapshot completes.

Adaptations to Non-FIFO and Dynamic Networks

In modern distributed computing environments where communication protocols (such as UDP or multi-path TCP) do not guarantee FIFO message delivery, the classic Chandy-Lamport protocol must be adapted.

Advanced algorithms, including the Mattern and Spezialetti-Kearns snapshot algorithms, utilize vector clocks, message coloring, or acknowledgement tokens to track message states across non-FIFO topologies. In distributed databases and cloud platforms, snapshot isolation techniques (such as Multi-Version Concurrency Control, MVCC) implement related causal consistency ensures to ensure read consistency across globally distributed transaction shards.

References

  1. Chandy, K. M., & Lamport, L. (1985). "Distributed snapshots: Determining global states of distributed systems." ACM Transactions on Computer Systems, 3(1), 63–75. doi:10.1145/214451.214456
  2. Babaoglu, O., & Marzullo, K. (1993). "Consistent global states of distributed systems: Fundamental concepts and mechanisms." ACM Computing Surveys, 25(4), 635–646. doi:10.1145/224056.224075
  3. Lamport, L. (1978). "Time, clocks, and the ordering of events in a distributed system." Communications of the ACM, 21(7), 558–565. doi:10.1145/357172.357176
🧬 Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
💡 Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision