Introduction

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.

Run the Snapshot

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

<p class="hint">Three nodes — <b>A → B → C</b> — pass tokens continuously. Click <b>Step</b> to advance time; click <b>Snapshot!</b> to trigger the Chandy-Lamport marker protocol. Watch how each node records its local state and the in-transit tokens become the channel state.</p>
<div id="scene"></div>
<div id="log"></div>
<div class="btns">
  <button id="btn-step">Step</button>
  <button id="btn-snap">Snapshot!</button>
  <button id="btn-reset" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Chandy-Lamport global snapshot demo.
// System: 3 nodes A→B→C with FIFO channels. Tokens flow A→B and B→C each step.
// Snapshot: initiated by A. Marker travels A→B→C; each node records state on
// first marker receipt; channel state = tokens that arrived before marker closed.

const NODES = ['A', 'B', 'C'];

function initState() {
  return {
    // tokens held at each node
    held: { A: 3, B: 2, C: 1 },
    // in-transit queues for channels A→B and B→C (each is an array of items)
    // items are either 'token' or 'marker'
    ch: { AB: [], BC: [] },
    // snapshot recording per node: null = not recorded, else { tokens, step }
    snap: { A: null, B: null, C: null },
    // channel state recording: recorded after marker passes, captures pre-marker tokens
    chanSnap: { AB: null, BC: null },
    // which channels are "open" (still accepting tokens into channel state)
    // After a node records, it starts watching incoming channels for channel state
    watching: { AB: false, BC: false },
    // tokens captured for channel state (tokens that arrived while watching)
    chanCapture: { AB: [], BC: [] },
    snapshotStarted: false,
    snapshotDone: false,
    step: 0
  };
}

let S = initState();
const logEl = document.getElementById('log');

function log(msg, cls = 'info') {
  const d = document.createElement('div');
  d.className = cls;
  d.textContent = fmt('[step %step%] %msg%', { step: S.step, msg: msg });
  logEl.appendChild(d);
  logEl.scrollTop = logEl.scrollHeight;
}

function render() {
  const scene = document.getElementById('scene');
  scene.innerHTML = '';

  // Helper: render a node box
  function nodeEl(id) {
    const div = document.createElement('div');
    div.className = 'node' + (S.snap[id] ? ' recorded' : '');
    const lbl = document.createElement('div');
    lbl.className = 'node-label';
    lbl.textContent = id;
    const tok = document.createElement('div');
    tok.className = 'node-tokens';
    tok.textContent = fmt('tokens: %v%', { v: S.held[id] });
    const st = document.createElement('div');
    st.className = 'node-state';
    if (S.snap[id]) st.textContent = fmt('snap@%step%: %tokens%', { step: S.snap[id].step, tokens: S.snap[id].tokens });
    div.appendChild(lbl); div.appendChild(tok); div.appendChild(st);
    return div;
  }

  // Helper: render a channel
  function chanEl(key) {
    const div = document.createElement('div');
    div.className = 'channel';
    const arr = document.createElement('div');
    arr.className = 'channel-arrow';
    arr.textContent = '→';
    const msgs = document.createElement('div');
    msgs.className = 'channel-msgs';
    S.ch[key].forEach(item => {
      const t = document.createElement('div');
      t.className = 'token' + (item === 'marker' ? ' marker' : '');
      t.textContent = item === 'marker' ? 'M' : '●';
      msgs.appendChild(t);
    });
    const cst = document.createElement('div');
    cst.className = 'channel-state';
    if (S.chanSnap[key] !== null) {
      cst.textContent = fmt('ch: %v%', { v: S.chanSnap[key] });
    }
    div.appendChild(arr); div.appendChild(msgs); div.appendChild(cst);
    return div;
  }

  scene.appendChild(nodeEl('A'));
  scene.appendChild(chanEl('AB'));
  scene.appendChild(nodeEl('B'));
  scene.appendChild(chanEl('BC'));
  scene.appendChild(nodeEl('C'));

  document.getElementById('btn-snap').disabled = S.snapshotStarted;
}

function doStep() {
  S.step++;

  // 1. Deliver one item from each channel (FIFO)
  function deliver(ch, to) {
    if (S.ch[ch].length === 0) return;
    const item = S.ch[ch].shift();
    if (item === 'marker') {
      // The receiving node processes the marker
      if (!S.snap[to]) {
        // First marker: record state
        S.snap[to] = { tokens: S.held[to], step: S.step };
        log(fmt('Node %to% received marker → records state:  tokens=%v%', { to: to, v: S.held[to] }), 'ok');
        // Start watching incoming channel for channel state (already captured what arrived before)
        S.chanSnap[ch] = S.chanCapture[ch].length;
        log(fmt('Channel %ch% state sealed: %length% in-transit token(s)', { ch: ch, length: S.chanCapture[ch].length }), 'mark');
        S.watching[ch] = false;
        // Forward marker if not the last node
        if (to === 'B') { S.ch['BC'].push('marker'); log('Node B forwards marker → BC', 'mark'); }
        if (to === 'C') {
          // Done
          S.snapshotDone = true;
          log(fmt('Snapshot complete! Global state = A:%tokens% B:%tokens2% C:%tokens3% | ch AB:%AB% ch BC:%BC%', { tokens: S.snap.A.tokens, tokens2: S.snap.B.tokens, tokens3: S.snap.C.tokens, AB: S.chanSnap.AB, BC: S.chanSnap.BC }), 'ok');
        }
      } else {
        // Subsequent marker on same channel: just seal channel state
        S.chanSnap[ch] = S.chanCapture[ch].length;
        log(fmt('Duplicate marker on %ch% ignored; ch state sealed: %length%', { ch: ch, length: S.chanCapture[ch].length }), 'mark');
        S.watching[ch] = false;
      }
    } else {
      // Regular token delivered
      if (S.watching[ch]) {
        // This token arrived before the marker on this channel → channel state
        S.chanCapture[ch].push('token');
      }
      S.held[to]++;
      log(fmt('Token delivered on %ch% → %to% now holds %v%', { ch: ch, to: to, v: S.held[to] }));
    }
  }

  // Deliver from BC first, then AB (order within step doesn't matter for FIFO)
  deliver('BC', 'C');
  deliver('AB', 'B');

  // 2. Node A sends a token to B each step (normal operation)
  if (S.held.A > 0) {
    S.held.A--;
    S.ch.AB.push('token');
  }
  // 3. Node B passes one token to C each step if it has tokens
  if (S.held.B > 0) {
    S.held.B--;
    S.ch.BC.push('token');
  }

  render();
}

function doSnapshot() {
  if (S.snapshotStarted) return;
  S.snapshotStarted = true;
  S.step++;
  // A records its own state immediately
  S.snap.A = { tokens: S.held.A, step: S.step };
  log(fmt('Snapshot initiated by A → records state: tokens=%A%', { A: S.held.A }), 'ok');
  // A sends marker on AB; start watching AB for channel state
  S.ch.AB.push('marker');
  S.watching.AB = true;
  log('A sends marker on channel AB', 'mark');
  render();
}

function doReset() {
  S = initState();
  logEl.innerHTML = '';
  render();
}

document.getElementById('btn-step').addEventListener('click', doStep);
document.getElementById('btn-snap').addEventListener('click', doSnapshot);
document.getElementById('btn-reset').addEventListener('click', doReset);

render();
Result
Console

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 Real Complexity

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)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).

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/chandy-lamport/Content licensed under CC BY-NC 4.0.