Chandy–Lamport Distributed Snapshot
The Chandy–Lamport distributed snapshot algorithm captures a consistent global state of an asynchronous distributed system without halting ongoing computations or synchronizing physical clocks.
The Chandy–Lamport distributed snapshot algorithm is a fundamental distributed algorithm formulated in 1985 by computer scientists K. Mani Chandy and Leslie Lamport to record a consistent global state (a snapshot) of an asynchronous distributed system during ongoing computation. In distributed systems lacking a shared physical clock or shared memory, determining global properties—such as detecting process deadlocks, identifying distributed termination, or establishing valid checkpoint restart points for fault tolerance—is notoriously difficult because independent processes communicate primarily via message-passing channels with variable, unpredictable transmission latencies.
The Chandy–Lamport protocol solves this problem without freezing system execution or halting underlying application transactions. By interleaving special control messages called markers with regular application messages along First-In, First-Out (FIFO) communication channels, the algorithm ensures that the recorded global state forms a consistent cut across space and time.
System Model and Core Assumptions
The algorithm operates within a standard asynchronous distributed computing model governed by well-defined topological and network ensures.
The distributed system consists of a finite graph of processes interconnected by unidirectional communication channels. Processes communicate only by sending and receiving discrete messages, with processing steps and message propagation delays being finite but arbitrary.
If communication channels are non-FIFO, the protocol cannot guarantee consistency without additional sequence-number tracking or vector clock mechanisms, making FIFO ordering a foundational structural assumption.
Consistent Cuts and Global State Definitions
The theoretical correctness of the algorithm is rooted in the concept of a consistent cut, formalized by Lamport's happens-before relation (denoted by the causal arrow →).
A global state S is defined as the union of the local states of all individual processes plus the states of all communication channels. A recorded global state is defined as consistent if and only if, for every message m in the system:
In terms of spacetime diagrams, a consistent cut represents a dividing line across all process worldlines such that no causal event in the future of the cut influences an event in the past of the cut. An inconsistent snapshot would capture "orphan messages"—messages received in the recorded process state whose corresponding transmission event does not exist in the sender's recorded state, violating causality.
Algorithmic Execution: The Marker Rule
The protocol can be initiated concurrently by one or more processes without prior coordination. The entire algorithm is defined by two simple, elegant operational rules: the Marker-Sending Rule and the Marker-Receiving Rule.
Because channels follow FIFO ordering, the arrival of marker M along channel C(P→Q) acts as a definitive temporal separator: any application message sent by P before P sent the marker arrives at Q before the marker, while any message sent by P after the marker arrives at Q after the marker.
Algorithmic Termination and Snapshot Assembly
The snapshot protocol terminates locally at process Q once Q has received a marker along every one of its incoming channels.
Once all processes have terminated the protocol locally, the distributed snapshot is complete. The global state consists of the set of all recorded local process states alongside the recorded message queues representing messages that were in transit along channels at the moment the snapshot cut crossed those channels. These local state records can then be gathered at a designated coordinator node via distributed reduction or spanning tree aggregation to assemble the composite global picture.
Meaning of the Recorded State
A fundamental property of the Chandy-Lamport snapshot is that the recorded global state may not have occurred at any single instant of physical real time.
Because communication delays are asynchronous, process P may record its state hours before process Q records its state. However, the recorded state is guaranteed to be causally consistent: it represents a valid global state that the distributed system could have passed through along a valid serialization of events. If a stable property (such as deadlock or termination) holds in the recorded state, that property holds in the actual system at the moment the snapshot completes.
Adaptations to Non-FIFO and Dynamic Networks
In modern distributed computing environments where communication protocols (such as UDP or multi-path TCP) do not guarantee FIFO message delivery, the classic Chandy-Lamport protocol must be adapted.
Advanced algorithms, including the Mattern and Spezialetti-Kearns snapshot algorithms, utilize vector clocks, message coloring, or acknowledgement tokens to track message states across non-FIFO topologies. In distributed databases and cloud platforms, snapshot isolation techniques (such as Multi-Version Concurrency Control, MVCC) implement related causal consistency ensures to ensure read consistency across globally distributed transaction shards.
References
- Chandy, K. M., & Lamport, L. (1985). "Distributed snapshots: Determining global states of distributed systems." ACM Transactions on Computer Systems, 3(1), 63–75. doi:10.1145/214451.214456
- Babaoglu, O., & Marzullo, K. (1993). "Consistent global states of distributed systems: Fundamental concepts and mechanisms." ACM Computing Surveys, 25(4), 635–646. doi:10.1145/224056.224075
- Lamport, L. (1978). "Time, clocks, and the ordering of events in a distributed system." Communications of the ACM, 21(7), 558–565. doi:10.1145/357172.357176