The idea: a photo of a system that never stops
A global snapshot is the state of every process and of every message still travelling between them. You need one to save a checkpoint, to detect that a computation has finished or deadlocked, or simply to count something that is spread over many machines. The difficulty: there is no shared clock and no way to freeze every process at the same instant, and stopping the whole system to take the picture is usually not allowed. Chandy and Lamport (1985) showed how to take a correct snapshot while the system keeps running, using one extra message, the marker.
The page models a small bank: three branches P1, P2, P3 start with $100 each, so the bank always holds $300. Each pair of branches is linked by two one-way FIFO channels (P1→P2 and P2→P1, and so on: six in all). A transfer leaves the sender's balance when it is sent and reaches the receiver's balance when it is delivered; in between, the money is only in the channel. The line at the bottom of the network panel always shows balances + money in flight = $300.
| On the page | Meaning |
|---|---|
| boxes P1, P2, P3 | branches with their balance; blue once the branch has recorded its state, with the recorded amount next to it |
| lines with arrows | the six channels; the messages waiting in a channel sit beside its line, oldest nearest the receiver; grey = not recorded, orange = being recorded, green = closed |
| $30 and marker | a transfer (green box) and a marker (orange box) in flight |
| Chandy–Lamport panel | the recorded balance of each branch, the recorded state of each channel, and the total once the snapshot is complete |
| naive panel | balances copied one at a time with Read Balance, and their total |
Why reading every balance gives the wrong total
The obvious way is to ask each branch for its balance, one after the other. Each answer is correct at the moment it is given, but the moments differ, and money moves in between. Two things go wrong:
- Money in flight is lost. P1 sends $30 to P2. P1 is read after it sent ($70), P2 before the money arrives ($100): the $30 is in neither answer, and the total is $270 (Demo 1).
- Money is counted twice. P1 is read before it sends ($100), P2 after the $30 arrives ($130): the same $30 is in both answers, and the total is $330 (Demo 2).
The line joining the moments of the reads is called a cut. The second cut is inconsistent: it contains the receipt of the $30 but not its sending, a state the bank could never have been in. The first cut is consistent, but it still needs the channel's content to be complete. A correct snapshot needs both: a consistent cut, and the messages that cross it.
The marker rules
Any branch can start a snapshot (Start Snapshot). Every branch then follows the same two rules:
| Event | What the branch does |
|---|---|
| it starts the snapshot, or receives its first marker (on channel c) | records its own balance; sends a marker on every outgoing channel before sending anything else; starts recording every other incoming channel; c (if any) is recorded as empty |
| it receives a marker on a channel it is recording | stops recording that channel; the channel's state is every message received on it since the branch recorded |
The snapshot is complete when every branch has recorded and every channel has been closed by its marker. Each branch knows when its own part is done (it has received a marker on every incoming channel); collecting the parts in one place is a separate step that the algorithm does not fix. With n processes and a channel in each direction, a snapshot costs one marker per channel: n(n−1) markers, 6 here.
What goes into a channel's state
A transfer is in a channel's state exactly when it was sent before the sender recorded and received after the receiver recorded. "Sent before the sender recorded" is guaranteed because the sender put its marker into the channel at the moment it recorded, and channels are FIFO: whatever arrives before the marker was sent before it. "Received after the receiver recorded" is guaranteed because recording only starts then. In Demo 3, P2 sends $40 to P1; P1 starts the snapshot and records $100; then the $40 arrives while P1 is recording P2→P1, and P2's marker closes the channel later with state $40. The snapshot reads P1 $100 + P2 $60 + P3 $100 + $40 = $300.
The same demo has P1 send $30 to P3 right after it recorded. That transfer enters the channel behind P1's marker, so P3 records first and the $30 is not part of the snapshot: it belongs to the future. Without FIFO the $30 could overtake the marker, P3's recorded balance would include it, and P1's would not have lost it yet: $330. Over non-FIFO channels the algorithm needs extra information on every message (for example a "sent before / after recording" flag, as in Lai and Yang's variant).
The recorded global state may never have existed at one single instant, but it is consistent: it could have happened, and it is reachable from the state when the snapshot started and leads to the state when it ended. Totals and other stable properties (once true, they stay true, like "terminated" or "deadlocked") are therefore read correctly from it.
Several initiators, empty channels
Two branches may start at the same time without knowing of each other (Demo 4: P1 and P3). Each records itself and sends markers; a branch that has already recorded treats a marker from the other initiator as an ordinary "later marker". The result is still one consistent snapshot, here $100 + $75 + $100 with $25 recorded on P2→P3. To run snapshots one after another, real systems number them (a snapshot or epoch id in each marker).
When nothing is in flight, every channel is recorded as empty and the snapshot is just the balances (Demo 5). That is also the only case where reading every balance happens to work; the naive reader cannot know when it is in that case.
Where it is used
Apache Flink's checkpoints use asynchronous barrier snapshotting, a Chandy–Lamport variant: sources inject numbered barriers into the streams (the markers), each operator snapshots its state when barriers arrive, and with exactly-once alignment it holds back a faster input until the barrier arrives on the slower one, so no channel state needs to be stored. The source offsets go into the checkpoint, so a failed job restarts from them, for example from Kafka offsets (Kafka). Distributed debuggers and garbage collectors use snapshots to detect termination and deadlock. A database's own crash recovery does it differently, with one log and checkpoints on a single machine (Write-Ahead Log and Crash Recovery).
Happened-before and logical clocks, the ideas behind consistent cuts, are on Lamport Clocks. For agreeing on one replicated log instead of photographing independent processes, see Raft; for the guarantees replicas give their readers, Consistency Patterns and the CAP Theorem.
What the page leaves out
Failures: the algorithm assumes processes do not crash and channels lose nothing during the snapshot. Collecting the recorded parts into one place, and numbering successive snapshots. Non-FIFO channels (Lai–Yang, Mattern's algorithms). Recording a channel by logging every message instead of only the ones in the window, and Flink's aligned and unaligned checkpoints. Simplifications: there is no clock, every action is one send, delivery or read; Deliver Next always delivers the oldest message, so messages never race on different channels unless a demo picks the channel; a channel holds at most 2 transfers; a new snapshot can start only after the previous one is complete.