Chandy-Lamport Global Snapshot

Imagine trying to photograph a busy road by taking separate snapshots of each lane at different moments. Some cars appear in two photos; others vanish completely. The picture is useless — it shows a state the road never actually had.

Distributed systems face this exact problem. A bank cluster might run on dozens of servers, each keeping its own local state. At any moment, messages are in transit between them — money wired from one account, a reply still flying through the network. If you want to know the total balance across all accounts, or checkpoint the whole cluster for recovery, you need a globally consistent snapshot: a record of every node's state and every in-flight message, taken at a moment that could have existed in some valid execution.

In 1985, K. Mani Chandy and Leslie Lamport published their landmark algorithm that does exactly this — without stopping the system, locking any process, or coordinating a global clock. Every node keeps running; a lightweight "marker" message ripples through the channels and each node records its own state when the marker first arrives. The messages caught between the marker and the snapshot form the channel state. At the end, the pieces compose into a globally consistent view.

The algorithm is proven correct (Chandy & Lamport, 1985): the resulting global state is a consistent cut — a snapshot that satisfies causality and could appear in a real execution. It runs in time proportional to the number of channels, and it is the foundation of every checkpoint, deadlock detector, and distributed garbage collector built since.

Below is a three-node pipeline — A → B → C — where tokens flow continuously. The snapshot is triggered by node A.

<p class="hint">{{hint}}</p>
<div id="scene"></div>
<div id="log"></div>
<div class="btns">
  <button id="btn-step">{{btn_step}}</button>
  <button id="btn-snap">{{btn_snap}}</button>
  <button id="btn-reset" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#scene { display: flex; align-items: center; gap: 0; margin: .5rem 0 .6rem; flex-wrap: nowrap; }
.node { width: 72px; height: 72px; border-radius: 12px; border: 2px solid #1d3557;
        display: flex; flex-direction: column; align-items: center; justify-content: center;
        background: #e8eef3; flex-shrink: 0; transition: background .3s; }
.node.recorded { background: #c7f0d8; border-color: #0a7d33; }
.node-label { font-weight: 700; font-size: 1.1rem; color: #1d3557; }
.node-tokens { font-size: .78rem; color: #444; margin-top: 2px; }
.node-state { font-size: .7rem; color: #0a7d33; font-weight: 600; min-height: 1em; }
.channel { flex: 1; display: flex; flex-direction: column; align-items: center;
           justify-content: center; position: relative; min-width: 60px; }
.channel-arrow { font-size: 1.1rem; color: #888; }
.channel-msgs { display: flex; gap: 3px; justify-content: center; flex-wrap: wrap;
                min-height: 20px; margin-top: 2px; }
.token { width: 18px; height: 18px; border-radius: 50%; background: #f4a261;
         border: 1.5px solid #c97a3b; display: flex; align-items: center;
         justify-content: center; font-size: .6rem; font-weight: 700; color: #fff; }
.token.marker { background: #1d3557; border-color: #0a2340; }
.channel-state { font-size: .68rem; color: #0a7d33; font-weight: 600;
                 min-height: 1em; text-align: center; }
#log { background: #f0f4f8; border: 1px solid #cdd9e3; border-radius: 8px;
       padding: .5rem .7rem; font-size: .8rem; line-height: 1.6; max-height: 150px;
       overflow-y: auto; margin-bottom: .6rem; font-family: ui-monospace, monospace; }
#log .ok { color: #0a7d33; font-weight: 600; }
#log .info { color: #1d3557; }
#log .mark { color: #c97a3b; font-weight: 600; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }

// Code not found

Watch what happens: A records its state first, then sends a marker downstream. B records when the marker arrives — any tokens that arrived at B before the marker (but after B's state was recorded) are captured as the channel state of A→B. The same logic applies to C. At the end, the three local snapshots plus the channel states form a consistent global snapshot.

The algorithm looks simple, but its correctness depends on subtle ideas in distributed systems theory.

Why naive approaches fail: you cannot just ask every node to record its state simultaneously — clocks differ, and "simultaneous" is meaningless without a global clock. You cannot pause every process — that defeats the purpose. Any snapshot that ignores in-flight messages will be inconsistent.

Lamport's happened-before relation (→): event e happened before event f if e causally could have influenced f — either they are on the same process in order, or e sent a message that f received. This gives a partial order on events without any physical clock.

Consistent cut: a cut is a partition of all events into "before the snapshot" and "after." It is consistent if whenever f is before the cut and e → f, then e is also before the cut. Informally: no effect appears without its cause. Chandy-Lamport guarantees the resulting cut is consistent.

The marker rule enforces this: when a process receives a marker on a channel for the first time, it records its state. Any message that arrives after the marker on the same channel was sent after the snapshot point — causality is intact. Messages that arrived before the marker on that channel are recorded as channel state.

Complexity: $O(N + E)$ time and message complexity (N processes, E channels), where each marker traverses each channel exactly once. The algorithm is proven correct in the original 1985 paper via invariants over consistent cuts.

What it does not solve: Chandy-Lamport assumes FIFO channels (messages arrive in order). Non-FIFO systems need additional sequence numbers. It also does not detect current deadlock — only the state at the snapshot moment. For live deadlock detection, you must take repeated snapshots and compare. These limitations are well-understood and addressed in later algorithms (e.g., distributed deadlock detection shares related ideas about global properties).

The ability to capture a consistent global state without stopping a system unlocks a remarkable range of practical capabilities:

• Fault-tolerant checkpointing: long-running distributed jobs (MapReduce, Flink, Spark Streaming) take periodic Chandy-Lamport snapshots. On failure, they restart from the last clean checkpoint rather than from scratch — Flink's "savepoint" is essentially this algorithm.
• Distributed garbage collection: the JVM and other runtimes must reclaim memory across nodes. A consistent snapshot lets the collector identify all live references spanning nodes; any object unreachable in the snapshot is garbage.
• Deadlock and termination detection: a snapshot captures the "waiting-for" graph; if every node is waiting for another, the deadlock is visible in the snapshot. Termination detection (has computation finished?) uses the same mechanism.
• Distributed debugging and monitoring: tools like distributed tracing (Jaeger, Zipkin) reconstruct global execution states from logged events — the same consistent-cut idea, applied after the fact.
• Database replication: consistent snapshots let secondary replicas catch up without interrupting the primary; PostgreSQL's logical replication and many cloud databases use snapshot-based change-data-capture.

The Chandy-Lamport insight — that a consistent global view can be assembled from local views if you respect causal order — also underpins distributed consensus protocols, where nodes must agree on a single global state despite failures.

Chandy and Lamport's 1985 algorithm solves one of the most deceptively hard problems in distributed computing: how do you take a picture of a moving system? The answer is elegant — send a marker, record local states, capture in-flight messages — and the result is provably correct without needing a global clock or any process to pause.

Every fault-tolerant distributed system you use today — from Google's Spanner to Apache Flink to cloud databases — relies on ideas rooted here. The next time a streaming pipeline recovers from a crash in seconds rather than hours, or a distributed debugger shows you the exact moment a bug emerged, you are seeing Chandy-Lamport at work.

The algorithm is a reminder that in distributed computing, the hardest problems often come down to time and causality. Once you have Lamport's happened-before in your toolkit, impossibility shrinks and elegant solutions appear.