eduKate Sengkang

Small Group Tutorials

Here to help students catch up, keep up, and move ahead. Book a consultation here.

Chat on WhatsApp

How to Learn the Chandy–Lamport Snapshot Algorithm: Markers, Channel State, Consistent Cuts and Distributed Checkpoints

Quick Read. The Chandy–Lamport snapshot algorithm records a consistent global state of an asynchronous distributed system without stopping the computation. The beginner should learn why “read every machine now” is not a well-defined operation when messages are in flight. The intermediate learner should understand marker messages, local-state recording and incoming-channel recording. The advanced learner should understand consistent cuts and the FIFO-channel proof. The professional should understand assumptions, failure boundaries, checkpointing systems, barrier variants, recovery semantics and how to test a snapshot implementation under adversarial message timings.

One-sentence answer

The Chandy–Lamport algorithm obtains a consistent distributed snapshot by having processes record local state and send marker messages through FIFO channels so that messages crossing the logical snapshot boundary are captured as channel state rather than lost or counted in the wrong era.

Why a distributed snapshot is harder than a photograph

Imagine three computers maintaining pieces of one system. While you read the state of Computer A, A may send a message to B. Before you read B, B may process that message and change its state. If you simply collect the three local states one after another, the result may describe a global situation that never existed.

The missing object is the communication channel. A message may have been sent before the snapshot boundary but not yet received. That message is part of the global state too. A correct distributed snapshot therefore needs two kinds of information: the local state of every process and the state of messages in transit on communication channels.

Level 1 — Beginner: the bank-transfer thought experiment

Suppose Process A holds an account balance of $100 and Process B holds $100. A sends a transfer of $20 to B. The message is currently travelling through the channel.

  • If you record A after it has deducted $20, A shows $80.
  • If you record B before it receives the message, B still shows $100.
  • If you ignore the in-flight transfer, the snapshot appears to contain only $180.
  • The missing $20 is not gone; it lives in the channel state.

This example teaches the central idea: global state is not merely the sum of machine memories. Communication in flight matters.

The marker idea

Any process may initiate a snapshot. It first records its own local state. Then, before sending further application messages on each outgoing channel, it sends a special marker on that channel.

Because the classical algorithm assumes FIFO channels, a marker divides a channel’s message stream into two logical regions. Messages that arrived before the marker were sent before the sender’s snapshot boundary. Messages sent after the marker belong to the post-snapshot future.

Level 2 — Intermediate: what a process does on the first marker

Suppose process P has not yet recorded its snapshot state. It receives a marker for the first time on incoming channel C.

  • P records its local state immediately.
  • P records the state of channel C as empty. Under FIFO ordering, every message sent on C before the sender’s marker has already arrived before that marker.
  • P sends a marker on every outgoing channel before sending any subsequent application message on those channels.
  • P begins recording application messages arriving on each other incoming channel.

Why record the other incoming channels? Their senders may already have taken their snapshots, but P has not yet received their markers. Messages arriving in that interval were sent before the corresponding remote snapshot boundary but received after P recorded its own local state. Those are precisely the in-flight messages that belong in channel state.

What happens on a later marker?

If P has already recorded its local state and later receives a marker on another incoming channel D, P stops recording messages for D. The messages accumulated on D since P’s local snapshot are the recorded state of that channel.

on initiate_snapshot():
    record local state
    for each outgoing channel:
        send MARKER before any later application message
    start recording every incoming channel

on receive MARKER on channel c:
    if local state not yet recorded:
        record local state
        record c as empty
        send MARKER on every outgoing channel
        start recording all other incoming channels
    else:
        stop recording c
        saved messages on c are c's channel state

This pseudocode exposes the conceptual shape. A real implementation also needs snapshot identifiers, concurrent-snapshot handling, storage, channel bookkeeping, failure policy and lifecycle management.

Consistent cuts: the idea behind correctness

A distributed execution can be drawn as one timeline per process with message arrows between them. A snapshot corresponds to cutting across these timelines. The cut is consistent when it never contains the receipt of a message without also accounting for its send. Informally: a snapshot should not contain an effect while excluding its cause.

The recorded process states plus recorded channel states form such a consistent cut. A message crossing the cut is not misplaced; it is captured as in-flight channel state.

Level 3 — Advanced: why FIFO channels make markers work

Suppose process A records its state and then sends a marker on channel A→B before any later application message. Since the channel is FIFO, B cannot receive a post-snapshot application message from A before receiving A’s marker. The marker therefore safely separates pre-snapshot traffic from post-snapshot traffic on that channel.

This is the key proof mechanism. The marker is not a global clock. It is a per-channel delimiter whose ordering is guaranteed by FIFO delivery.

  • If B receives A’s marker before B has recorded its state, then every earlier A→B application message has already arrived and is reflected in B’s local state.
  • If B had already recorded its state, it records application messages from A until A’s marker arrives; those messages are exactly the A→B messages that crossed the cut.
  • Messages arriving after the marker were sent after A’s recorded state and therefore belong after the snapshot boundary.

What the classical algorithm assumes

The original algorithm is elegant partly because its model is explicit. Learn the assumptions before learning the steps.

  • Communication channels are unidirectional and FIFO.
  • Messages are delivered reliably under the model; they are not silently lost, duplicated or corrupted.
  • Processes do not fail during the snapshot protocol in the classical correctness model.
  • The computation continues while the snapshot is taken.
  • The communication topology lets markers propagate to the participating processes.

If your real system violates these assumptions, do not merely paste the classical pseudocode into production. Non-FIFO channels, failures, retries, duplicated messages, exactly-once processing and partial membership each require additional protocol design.

Stable properties: what snapshots let you detect

Chandy and Lamport motivated the method partly through stable properties: properties that, once true, remain true. Examples include certain forms of termination and deadlock. A consistent global state can let a system reason about such conditions without demanding a physically simultaneous observation of every process.

This gives a broader lesson: distributed algorithms often replace impossible simultaneity with a logically consistent representation.

Level 4 — Professional: snapshots in modern stream processing

Modern stateful dataflow systems use related ideas for fault-tolerant checkpointing. Apache Flink’s current documentation describes consistent state snapshots and explicitly says its checkpointing mechanism is inspired by the Chandy–Lamport algorithm, adapted to the dataflow execution model. Flink injects checkpoint barriers into streams; the barriers separate records that belong before and after a checkpoint.

This is a valuable professional connection, but do not collapse the two systems into one. A production stream processor has source offsets, operator state, durable storage, recovery coordination, alignment choices, unaligned checkpoints, connector guarantees and sink semantics that go beyond the classical paper.

Checkpointing is only useful if recovery semantics are defined

A snapshot is not a complete fault-tolerance story by itself. Professionals must ask what input position is restored, whether external side effects are replay-safe, how state is persisted, what happens if the snapshot itself fails, how long retention lasts and which guarantees the source and sink connectors actually provide.

Testing ladder

  • Two processes, one channel: test marker before any application message, after several messages, and while one message is in flight.
  • Two-way communication: ensure each directed channel is recorded independently.
  • Three-process ring: vary marker delays heavily while keeping FIFO ordering.
  • Money-conservation invariant: local balances plus in-flight transfers should preserve total value.
  • Concurrent application traffic: continue sending while a snapshot executes and verify no effect appears without its cause.
  • Multiple snapshot IDs: ensure state from overlapping snapshots does not mix.
  • Model-violation tests: deliberately reorder or drop messages in a simulator and confirm that the implementation detects or documents unsupported behaviour rather than silently claiming correctness.

Common misconceptions

  • “All processes freeze at the same instant.” They do not. The algorithm records different local states at different real times but combines them into a consistent global state.
  • “A marker records the whole channel.” It delimits which application messages belong before or across the snapshot boundary.
  • “The snapshot contains only process memory.” In-flight channel state is essential.
  • “A consistent snapshot is necessarily the latest possible state.” Consistency and recency are different properties.
  • “The classical protocol automatically handles crashes and non-FIFO delivery.” Those are outside its basic assumptions.

A learning route from beginner to professional

  • Beginner: draw two process timelines and account for one in-flight transfer.
  • Intermediate: trace first-marker and later-marker rules by hand on a three-process example.
  • Advanced: draw the corresponding cut and explain why it is consistent.
  • Implementation: build a deterministic simulator with explicit FIFO channels and snapshot IDs.
  • Professional: introduce message delays, overlapping snapshots, durable storage and recovery, then compare your model with production barrier/checkpoint designs.

Programming-education research supports this trace-first approach. Recent work on novice program tracing shows that misconceptions can persist across experience levels, while worked examples and carefully guided explanations can reduce cognitive load. For this algorithm, timeline diagrams are not decoration; they are one of the best ways to make causality visible.

Authoritative sources and further reading

Closing idea. The Chandy–Lamport algorithm teaches one of distributed computing’s deepest habits: when “now” cannot be observed everywhere at once, define a representation that preserves causality strongly enough for the decision you need to make.