The Chandy-Lamport Distributed Snapshot Algorithm

The Problem: Capturing a Moment in a System With No Clock

A distributed system consists of processes that communicate only by sending messages along channels, with each process knowing nothing about the others' current state except through those messages. There is no global clock and no instant at which every machine can be told to pause simultaneously, because the very act of telling them takes time and arrives at different moments. This creates a real difficulty: if you ask every process to report its state whenever it happens to receive your request, the reports will reflect wildly different, uncoordinated instants, and some may even describe a state that never truly existed together. For example, one process might report having already received a message that, according to another process's report, had not yet been sent. Such a snapshot would be inconsistent and could mislead any algorithm relying on it, such as one checking whether the system has enough resources or has deadlocked. What is needed instead is a consistent global state, sometimes called a consistent cut: a collection of local states, one per process, plus the set of messages in transit on each channel, such that the collection could have plausibly existed at a single instant according to the causal order of events. Crucially, this does not require real-time simultaneity. It only requires that the recorded states respect causality: if the snapshot records that a message was received, it must also record that the same message was sent. The Chandy-Lamport algorithm was designed specifically to produce such a cut efficiently, using only the messages the system already sends, plus one new kind of message called a marker, and it assumes channels are reliable and deliver messages in the order they were sent (FIFO), which is essential to how the algorithm reasons about what it has and has not yet seen.

How the Algorithm Works: Markers, Recording, and Propagation

The algorithm begins when any single process decides to initiate a snapshot. That initiating process first records its own local state, capturing whatever internal variables matter for the application, and then immediately sends a special marker message out along every one of its outgoing channels, before doing anything else. This marker carries no application data; its only purpose is to signal a snapshot boundary. From that point on, the initiator also begins recording every application message it receives on each of its incoming channels, treating those messages as the in-transit state of that channel, until a marker arrives there. Now consider any other process in the system. The first time it receives a marker, on some incoming channel, it does two things immediately: it records its own local state, exactly as it exists at that moment, and it records the state of the channel the marker arrived on as empty, since a marker on a FIFO channel signifies that no earlier application messages remain unaccounted for on that link. It then propagates the snapshot by sending a marker out on all of its own outgoing channels, just like the initiator did, and it begins recording incoming messages on every other channel it has not yet seen a marker on. If a process later receives a marker on one of those other channels, it stops recording that channel and finalizes its recorded list of in-flight messages for it, which is precisely the set of messages it received on that channel after recording its own state but before the marker arrived. If a process receives a second or subsequent marker on a channel it has already seen a marker on, it simply closes out that channel's recording, since a duplicate marker on the same channel signals no new information. The algorithm terminates once every process has received a marker on every one of its incoming channels, at which point every local state and every channel state has been recorded, and the complete global snapshot can be assembled, typically by having each process forward its recorded state to a coordinator.

Why the Snapshot Is Consistent: The Cut Argument

The heart of Chandy-Lamport's correctness proof is showing that the collection of recorded states forms a genuinely consistent cut, meaning that for every message the snapshot marks as received by some process, the same message is also accounted for as either recorded in the sender's pre-snapshot state, sent and captured as part of a channel's in-flight state, or otherwise consistently placed. The key insight is the strict ordering enforced by markers combined with the FIFO property of channels. When a process P records its state and then sends markers on all outgoing channels, every application message P sends afterward is sent after the marker on that same channel, because a process never reorders its outgoing messages relative to when it decided to snapshot. Therefore any process Q that later receives that marker on the channel from P knows, by FIFO ordering, that every application message arriving on that channel before the marker was sent by P before P's snapshot, and everything arriving after belongs to the post-snapshot future and is correctly excluded from the in-flight recording. This guarantees the crucial property: no message can be recorded as received in the snapshot without its send also being reflected, either in the sender's recorded local state, having already happened, or in some channel's recorded in-flight messages. Put differently, the algorithm never captures an effect without its cause. This matters enormously for any algorithm consuming the snapshot, because it means the recorded global state, even though its pieces were physically observed at different real-world moments across the network, corresponds to a state the system could genuinely have passed through in a valid execution consistent with the actual order of events (its causal, or happened-before, order). That guarantee, not literal simultaneity, is what makes the snapshot trustworthy and usable for reasoning about global properties.

Practical Uses: Checkpointing and Deadlock Detection

The most direct application of Chandy-Lamport snapshots is checkpointing for fault tolerance. In long-running distributed computations, such as large scientific simulations or transaction processing systems, periodically saving a consistent global state lets the entire system recover from a crash by rolling back to the last checkpoint rather than restarting from scratch. Because the snapshot is guaranteed consistent, resuming from it never puts the system in an impossible state where a process appears to have received a message that, according to the recovered state, was never sent; the recorded channel contents are simply replayed as if freshly arrived. A second major use is distributed deadlock detection. In systems where processes hold resources and wait on each other, such as in distributed databases negotiating locks, a deadlock corresponds to a cycle in a global wait-for graph, but no single process can see that graph directly since each only knows its own local dependencies. By taking a consistent snapshot of every process's local resource and wait state, a monitoring algorithm can reconstruct the full wait-for graph exactly as it existed at one consistent instant and search it for cycles, and because the snapshot is provably consistent, a cycle found there corresponds to a real deadlock rather than an artifact of comparing mismatched moments in time. The algorithm has also influenced broader techniques for detecting stable properties, meaning properties that, once true, remain true, such as termination detection or garbage collection in distributed object systems, since a consistent snapshot is exactly the tool needed to safely evaluate whether such a property currently holds across an entire system without pausing it.

Assumptions, Limitations, and Design Trade-offs

Chandy-Lamport's elegance rests on a specific set of assumptions worth understanding clearly. It requires that channels are reliable, meaning no messages are lost, duplicated, or corrupted, and that they are FIFO, delivering messages in the exact order sent, since the correctness argument depends entirely on a marker acting as a reliable boundary within an ordered stream. It also assumes the underlying network is strongly connected, so that markers initiated anywhere can eventually reach every process, and that every process, once it receives a marker, correctly follows the protocol without failing partway through the snapshot itself. If channels can reorder or drop messages, the basic algorithm's guarantees break down and more elaborate variants with sequence numbers or acknowledgments are needed. The algorithm is also silent about what happens between the moment it detects a global property and the moment any action is taken on that information; since the system keeps running throughout, the snapshot describes a state that is already in the past by the time it is fully assembled, so its conclusions must be about stable properties or used for recovery, not for making instantaneous real-time control decisions. Another subtlety is overhead: the number of marker messages grows with the number of channels, and every process must temporarily buffer incoming messages on unmarked channels, which costs memory proportional to how quickly markers propagate. Despite these constraints, the algorithm's core contribution, decoupling the notion of a meaningful global snapshot from the impossible requirement of literal simultaneity, remains one of the foundational ideas in distributed systems theory, and its descendants appear throughout modern stream processing frameworks and distributed database checkpoint protocols.

Frequently asked questions

Try it live

Everything above runs in your browser — open The Chandy-Lamport Distributed Snapshot Algorithm and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.