CS PAPERS DEEP READ · PAPER 72

Distributed Snapshots

K. Mani Chandy & Leslie Lamport · ACM TOCS · 1985

What did this paper do?

In 1985, Chandy and Lamport gave a way to take a coherent photograph of an entire distributed system — without stopping it, and without any clock that every machine agrees on. When a stream engine like Flink saves its progress every few seconds and resumes from the last save after a crash, it is running this paper's idea.

Start with something odd

Say the system holds just two accounts, A and B, with 100 dollars between them, and you want to check the total. You ask A: "how much do you have?" — A says 100. But right after you hang up, A wires 50 to B. You ask B — B says 50. That adds up to 150. Fifty dollars appeared out of nowhere.

Reversing the order is just as bad: ask A first (already wired, 50 left), then B (the money is still in flight, still 0) — a total of 50, and money has vanished. You did not miscount. The problem is that your two questions did not happen at the same instant. And in a distributed system there is no such thing as "the same instant": no two clocks agree, and you cannot make the world hold still while you take a picture.

What is new here

The older options were to stop the system (which stops the business with it) or to synchronize clocks (which never gets accurate enough). This paper changed the goal instead: stop chasing "the same instant" and settle for "not self-contradictory." As long as the photo never shows "B received money that A has not sent yet" — an effect arriving before its cause — it is a legitimate photo, even if the system never actually looked like that at any single moment. For a great many questions, that is enough.

How it works

The trick is embarrassingly simple. It needs one thing: a red card.

Step one: any machine that wants a photo first writes down what it looks like right now (how much is in its account), then drops one red card onto every outgoing line, and carries on working. Nothing pauses.
Step two: when another machine sees a red card for the first time, it immediately writes down its own state and drops red cards onto all of its own outgoing lines. The cards spread across the whole network by themselves, and each machine photographs itself exactly once.
Step three, the clever one — record the money in transit too. Everything a machine receives on a line after writing down its own state but before the red card arrives on that line was "still on the road" at photo time, so it goes into the photo as well.

Why can't this contradict itself? Because a line is a queue: what is sent first arrives first. So the red card becomes a divider on that line: everything ahead of it was sent before the photo, everything behind it was sent after. The "after" messages can never get into the photo (no money appears from nowhere), and any "before" message not yet delivered is guaranteed to land inside the window between "I recorded myself" and "the card arrived" (no money vanishes). There is no conductor and nobody is paused — each machine watches only its own few lines and makes a local decision, and a globally coherent photo assembles itself.

What it bought us

With a photo in hand, a pile of questions that only make sense from outside the system become judgements about one static picture: is it deadlocked? is the work finished? is anyone still using this memory? Plus the most practical use of all — the save point: store the photo, and after a crash restart from it instead of from the beginning.

One honest caveat: the photo may describe a moment that never actually happened — it is merely coherent. So it cannot answer fleeting questions like "how long is the queue right now."

Remember this

You cannot capture "the same instant," so settle for a photo that is merely self-consistent: whoever wants a snapshot records itself first, then drops a marker onto every outgoing line; whoever receives a marker does the same and passes it on; and whatever arrives between "I recorded myself" and "the marker got here" was in flight at photo time and is recorded too. Nobody stops, nobody synchronizes clocks, and a globally consistent picture assembles itself.

Want the marker rules as the paper states them, the space-time picture of a consistent cut, and the theorem that the snapshot may never have existed? → Switch to the deep read

In one sentence

The Chandy–Lamport snapshot algorithm: any process may spontaneously record its own state and then, before sending any further ordinary message, send a marker down each outgoing channel; every other process records its state the first time a marker reaches it and forwards markers in turn. Because channels are FIFO, the marker draws a clean line on each channel between "sent before the snapshot" and "sent after it," and each process records as the channel state whatever arrived between recording itself and receiving that channel's marker. With no pause, no locking and no global clock, the system assembles a causally consistent global state — one the system may never actually have passed through, yet good enough to decide any stable property (deadlock, termination, garbage).

Glossary

Process: an independently running unit with its own memory — a machine or a service instance.
Channel: a one-way link between processes. The paper assumes it never loses or corrupts messages, with arbitrary but finite delay.
FIFO: on one channel, messages arrive in the order they were sent; nothing overtakes anything else. A TCP connection has this property.
Local vs. global state: a process's own memory is its local state; the global state is all local states plus every message still in flight in every channel. That second half is routinely forgotten, and it is the crux of this paper.
Event: one step a process takes — sending a message, receiving one, or computing internally — each of which may change its state.
Happens-before: the causal order Lamport defined in 1978 — earlier steps in a process precede later ones, a message's send precedes its receive, plus transitivity. It is the only reliable ordering a distributed system gets for free.
Cut: one slice through each process's event sequence; everything "before the slice" forms a candidate photograph.
Stable property: one that stays true forever once it becomes true — "the system is deadlocked," "the computation has terminated," "this object is garbage." The opposite is a fleeting predicate like "queue length > 10."
Deadlock / termination detection / garbage collection: respectively "a group of processes all waiting on each other," "every process idle and no messages in flight," and "nothing can reach this memory any more." All three are stable properties.
Checkpoint: a saved system state to restart from after a failure instead of starting over.

Where it sits

K. Mani Chandy (then at the University of Texas at Austin) and Leslie Lamport (then at SRI International) published "Distributed Snapshots: Determining Global States of Distributed Systems" in ACM Transactions on Computer Systems, February 1985. It is built directly on Lamport's own 1978 "Time, Clocks, and the Ordering of Events" — happens-before is the whole foundation here. Downstream it leads to the theory of consistent global states (Mattern's and Fidge's vector clocks), to FIFO-free variants (Lai–Yang), and to distributed checkpointing in industry. Lamport's own account is that Chandy posed the problem to him over dinner, that he worked out the solution in the shower the next morning, and that when he reached Chandy's office Chandy already had the same answer.

The problem and the motivation

The motivation was never "I would like a photograph." It was a very practical class of question: how do you tell that the system has entered some global state? Deadlock detection, termination detection and distributed garbage collection look unrelated, but they are the same thing underneath — step outside the system, look at the current global state, and decide whether a predicate holds.

Except "look at it" is exactly what a distributed system forbids. Two hard constraints: no shared memory (nobody can see anyone else's memory; you can only ask by message) and no global clock (no two clocks agree, and you cannot arrange for everyone to record "at 3 o'clock sharp"). So you must ask one at a time, and asking one at a time necessarily spans an interval during which the system keeps running — with the consequence shown by the bank example above. The paper's own opening image: a group of photographers must capture a sky filled with migrating birds; the scene is too large for one shot, so they shoot separately and combine, but the birds are flying and the shutters are not synchronized, so the composite may show some birds twice and miss others entirely. The hard part was never taking the picture; it was making the composite mean something.

And there is a half that is easy to miss: the global state is not merely the sum of the process states, it also includes every message in flight in every channel. Record only the processes, forget what is on the wire, and that is precisely how the missing 50 dollars goes missing. That half is half of this paper's contribution.

Core idea and method

Step one: swap "simultaneous" for "consistent"

Since "the same instant" is unobtainable, the paper adopts a different test: a photograph (a cut) is acceptable as long as it contains no causal inversion. A causal inversion is a message that appears in the photo as received although it was never sent — the receiver has recorded "I got it" while the sender has recorded "I have not sent it." Such a cut is inconsistent; otherwise it is a consistent cut.

In happens-before terms, a consistent cut is a causally closed prefix: if event b is in the cut and a happens before b, then a must be in the cut too. Note the asymmetry: "sent but not yet received" is perfectly legal — that is just a message in flight, to be recorded faithfully — whereas "received but not yet sent" describes a world that cannot exist and must be ruled out. The algorithm's whole job is to guarantee the latter never happens.

Fig. 1 · Horizontal lines are process timelines, diagonal arrows are messages, dashed lines are cuts. Left: the cut falls before A's send but after B's receive, producing money the receiver has and the sender never sent. Right: the cut catches the message in flight, which is simply recorded as channel state.

Step two: two rules, and there is no third

The algorithm introduces one special message, the marker. It takes no part in the computation; its only job is to draw a line on each channel. The entire algorithm is these two rules:

Marker-sending rule: process p first records its own state; then, before sending any further ordinary message along a channel c, it sends one marker down every outgoing channel. (The ordering — record first, marker next, ordinary messages last — is the whole key.)
Marker-receiving rule: when process q receives a marker along channel c — if q has not yet recorded its state, it records its state immediately, records the state of c as the empty sequence, and then follows the sending rule; if q has already recorded its state, it records the state of c as the sequence of messages received on c after q recorded its state and before this marker arrived.

A snapshot is initiated spontaneously by any process (it simply executes the sending rule); no permission is needed. Several initiators at once do no harm — each process records itself only on the first marker it sees, and later markers merely close off their own channels.

Fig. 2 · P initiates: it records itself, then sends a marker on every outgoing channel. Q and R record themselves on their first marker and forward. Message m, which reaches R after R records itself (290) but before P's marker arrives (360), is exactly what was still travelling on channel P→R at snapshot time, and is recorded as that channel's state. Some markers are omitted for clarity.

Step three: why this is guaranteed to be consistent

Think of "recording my state" as a process turning from white to red: messages sent before the recording are white (pre-snapshot), messages sent after are red. The two rules together guarantee one thing — on any channel, every white message sits ahead of the marker and every red message sits behind it.

Why? Two conditions mesh. The sending rule dictates record first, marker next, only then a red message, so the marker necessarily precedes every red message on that channel; and the channel is FIFO, so the order is not scrambled and the receiver sees exactly the order the sender produced. The marker is therefore a clean pair of scissors on the channel:

No red message can enter the photo — the receiver's window for recording channel state closes when the marker arrives, and every red message is behind it. (No money from nowhere; causal inversion is ruled out.)
Every white message is accounted for — either it arrived before the receiver recorded itself, in which case it is already reflected in the receiver's local state, or it falls inside the window between "receiver recorded itself" and "marker arrived," in which case it is recorded as channel state. (No money vanishes.)

The white/red boundary is exactly that cut, and the first bullet shows the cut is consistent. The argument needs no global coordination whatsoever: each process looks only at what it received, and global consistency falls out of FIFO plus the rule ordering.

Step four: cost and termination

Exactly one marker traverses each channel, so the message overhead is |E| (the number of channels), independent of application traffic. The ordinary computation never stops: recording your state is an instantaneous local act, after which you send and receive as usual. Provided one process initiates and the topology reaches all processes, the algorithm finishes in finite time (message delays are finite). One step remains — gathering the scattered fragments into one place to form the complete snapshot — and the paper leaves that to the application.

Step five: the photograph may never have existed

This is the most misunderstood and most worth-remembering point. The recorded global state S* need not be any instant the system actually passed through — it is stitched together from fragments recorded at different physical times.

What the paper proves is weaker and exactly sufficient: let S_i be the actual state when the algorithm started and S_φ the actual state when it finished; then S* is reachable from S_i, and S_φ is reachable from S*. Equivalently, there is a causally equivalent reordering of the real execution (concurrent events permuted) along which S* genuinely did occur. In plain terms: the snapshot depicts a world that could perfectly well have happened — it just happens not to be the one that did.

That is exactly enough to decide a stable property y: if y(S*) is true then, since S_φ is reachable from S*, the system really is y now; if y(S*) is false then, since S* is reachable from S_i and y is stable, the system was not yet y when the algorithm began. Both directions yield a statement about the real system.

Fig. 3 · The snapshot S* need not lie on the actual execution path, yet it is reachable from the starting state S_i and can reach the finishing state S_φ — which is all a stable property needs in order to be decided.

Key results

This is a theory paper: no experimental tables, no benchmark numbers. Honestly stated, its "results" are the algorithm, the correctness proof and an application framework, not performance curves. Three quantifiable claims:

Cost: exactly one marker per channel, |E| extra messages in total, independent of application traffic; one local state recording per process.
Non-intrusiveness: fully concurrent with the underlying computation — no process is paused, no channel is frozen, no clock synchronization is required.
Correctness: S* satisfies the reachability chain S_i → S* → S_φ, which yields the two directions of stable-property detection above. The paper reduces deadlock detection and termination detection to "take a snapshot, then run a centralized decision on it" — and that reduction is itself part of the result.

Why it matters

It turned "the global state of a distributed system" from a vague intuition into a computable, reasonable-about object. Before it, "what does the system look like right now" was barely a discussable question; after it, consistent cut and consistent global snapshot became standard vocabulary.

In theory: together with Lamport's 1978 happens-before, it grounds what can be observed in a distributed system at all. Vector clocks (Mattern, Fidge, 1988) were devised precisely to characterize consistent global states, and the whole line of distributed debugging and predicate detection grows from here.
Unifying the problems: deadlock detection, termination detection and distributed garbage collection — previously separate algorithms — were absorbed into a single template, "stable-property detection."
In industry: the most direct descendant is Apache Flink's Asynchronous Barrier Snapshotting, where the barriers injected periodically into the dataflow are markers and an operator "aligning" barriers across its inputs is the marker-receiving rule; that is what supports exactly-once semantics and failure recovery. More broadly, "save the state of a running distributed system without stopping it" is still done within this paper's reach.

Limitations and criticism

It leans hard on FIFO channels: the marker works as scissors only because nothing overtakes it. On non-FIFO channels the algorithm simply fails. Lai–Yang (1987) and others give FIFO-free variants at the price of colouring messages and recording send/receive histories — trading extra information for the lost ordering guarantee.
It is not fault-tolerant: the paper assumes processes do not crash and messages are not lost. But if a process dies mid-snapshot, markers stop propagating and the snapshot hangs — and fault tolerance is exactly what people most want snapshots for. Real checkpointing systems must add timeouts, retries and coordination.
Only stable properties: since S* may never have really occurred, conclusions drawn on the photo about unstable predicates ("queue length right now," "is an invariant violated right now") carry no guarantee about the real system.
Every process must be modified: each participant has to understand the marker rules and be able to buffer channel state. In a system assembled from heterogeneous components written by other people, that "everyone cooperates" premise is not cheap.
States and channels can be huge: the paper does not care what one recording costs, but in engineering that is the dominant cost — a high-throughput channel may hold enormous numbers of in-flight messages, and a large stateful operator's snapshot can run to gigabytes. Flink's later incremental snapshots and unaligned checkpoints (abandoning barrier alignment and recording in-flight data instead) are both repayments on this debt.
Topology assumptions: markers must reach every process along channels (the paper argues over strongly connected graphs); in modern systems with members joining and leaving, that premise takes extra work to maintain.

Takeaways

1. In one line: using a special message called a marker, photograph a running distributed system in a causally consistent way — without stopping it and without synchronized clocks.

2. The pain: with no shared memory and no global clock, "look at the current global state" means asking one process at a time, and that makes money appear or vanish — which is where deadlock detection, termination detection and distributed GC all got stuck.

3. The conceptual swap: give up "the same instant" and aim for a consistent cut — the photo must never show a message received that was never sent; "sent but not received" is entirely legal.

4. Global state = all process states plus every message in flight in every channel. That second half is the one people forget, and it is where the money goes missing.

5. The algorithm is two rules: send — "record yourself, then send a marker on every outgoing channel, and only then any further ordinary message"; receive — "on your first marker, record yourself and forward (that channel's state is empty); otherwise record as that channel's state whatever arrived between recording yourself and this marker."

6. Why it is correct: treat "recording state" as turning from white to red. The rule ordering puts the marker ahead of every red message, and FIFO keeps the order intact — so the marker is clean scissors: no red message enters the photo, and no white message is lost.

7. Cost: one marker per channel, |E| in total; fully concurrent with the computation — no pause, no locks, no clock synchronization.

8. The subtle part: S* may never have really happened, but S_i → S* → S_φ are reachable in order — it is a world that could have happened, which suffices for deciding stable properties.

9. Impact and limits: consistent cuts became standard vocabulary and Flink's barrier snapshots are a direct descendant; but the algorithm needs FIFO, tolerates no failures, covers only stable properties, requires every process to cooperate, and can produce very large states.