Chandy–Lamport Algorithm

Chandy–Lamport Algorithm is a distributed snapshot algorithm in computation and algorithms that captures a causally consistent global state—comprising the local memory state of every process and the in-transit message state of every communication channel—across an asynchronous distributed system without synchronized physical clocks or global execution freezes. Formulated by K. Mani Chandy and Leslie Lamport in 1985, the protocol coordinates state capture by propagating lightweight control tokens called marker messages along first-in, first-out (FIFO) directed communication channels.

In distributed systems and computational complexity theory, asynchronous nodes lack a shared global clock and communicate via variable-latency networks, making it impossible to instruct all processes to record their local states at an identical physical instant. If processes record their states independently at uncoordinated times, the combined snapshot can violate causality—for example, recording that process q received a bank transfer message m from process p while recording the state of p before p ever sent m (an orphan message that duplicates funds). By aligning local state capture with FIFO marker boundaries under Leslie Lamport's happens-before relation (→), the Chandy–Lamport algorithm constructs a consistent cut that underpins distributed deadlock detection, garbage collection, fault-tolerant checkpointing in Apache Flink stream processors, and vector clock debugging.

Asynchronous Process-Channel Graph and FIFO Assumptions

The Chandy–Lamport model represents a distributed system as a strongly connected directed graph G = (P, C), where P = {p₁, p₂, ..., p_N} is a finite set of N processes and C ⊆ P × P is a set of directed communication channels c_i,j = (p_i, p_j). The system satisfies four operational assumptions:

1. No Shared Memory or Global Clock: Processes share no physical memory and have no synchronized wall-clock time; all interaction occurs via message passing over channels in C.
2. Reliable, Error-Free Channels: Neither processes nor channels fail during the snapshot, and every sent message is eventually delivered intact with finite (but arbitrary and unbounded) delay.
3. FIFO Channel Ordering: Each directed channel c_i,j delivers messages in First-In, First-Out order: if p_i sends message m₁ before m₂ on c_i,j, then p_j receives m₁ before m₂.
4. Non-Blocking Application Execution: Snapshot recording runs concurrently with normal application computation and never delays or reorders application messages.

Consistent Cuts and the Happens-Before Invariant

Let e_i⁽¹⁾, e_i⁽²⁾, ... denote the sequence of local events (internal state transitions, send(m), and recv(m)) executed by process p_i, partially ordered by Lamport's happens-before relation (→). A cut of a distributed execution is a tuple of local prefix histories K = (h₁, h₂, ..., h_N), where h_i contains all events at process p_i up to the instant p_i records its local state σ_i.

A cut K is causally consistent if and only if it is closed under causal precedence:

In message-passing terms, a global state S^* = ({σ_i}_i∈P, {Φ_i,j}_(i,j)∈C) is consistent if:

1. No Orphan Messages: Whenever recv(m) at p_j belongs to the recorded prefix h_j (a post-recording event cannot cause a pre-recording effect), the corresponding send(m) at p_i must also belong to the recorded prefix h_i.
2. Precise Channel In-Transit State: For each channel c_i,j, the recorded channel state Φ_i,j equals the precise sequence of messages that were sent by p_i before p_i recorded its state σ_i, but received by p_j after p_j recorded its state σ_j:

Initiation and the Two Atomic Protocol Rules

Any single process p_init ∈ P (or multiple processes concurrently) can initiate a global snapshot without prior coordination. The protocol is governed by two deterministic rules executed atomically with respect to local message handling:

1. Marker-Sending Rule for Process p_i:
   • Process p_i records its own local process state σ_i.
   • Before p_i sends any further application messages on any outgoing channel, p_i sends one marker message 〈MARKER〉 along every outgoing channel c_i,k (k = 1 .. d_out).
   • Process p_i initializes a message-logging buffer L_j,i ← ∅ for each of its incoming channels c_j,i and begins recording incoming application messages on those channels.

1. Marker-Receiving Rule for Process p_j (upon receiving 〈MARKER〉 on incoming channel c_i,j):
   • Case A (p_j has NOT yet recorded its local state σ_j):
   • Process p_j records its local process state σ_j.
   • Process p_j records the state of the incoming channel c_i,j on which this first marker arrived as empty: Φ_i,j ← ∅.
   • Process p_j executes the Marker-Sending Rule (sending 〈MARKER〉 on all its outgoing channels) and starts logging all application messages arriving on every other incoming channel c_k,j (k ≠ i).
   • Case B (p_j HAS ALREADY recorded its local state σ_j earlier):
   • Process p_j stops logging on incoming channel c_i,j and finalizes the recorded state Φ_i,j of channel c_i,j as the sequence of application messages received on c_i,j since p_j recorded its local state σ_j and before receiving 〈MARKER〉 on c_i,j.

When a process p_j has received a 〈MARKER〉 on every one of its incoming channels, its local snapshot (σ_j and all incoming channel states Φ_k,j) is complete and can be forwarded to an external collector.

Why FIFO + Markers Guarantee Consistency and Termination

Consider any channel c_i,j. Because p_i sends 〈MARKER〉 on c_i,j at the precise instant p_i records σ_i, and because c_i,j is FIFO, the marker partitions all messages ever sent on c_i,j into pre-snapshot messages (sent before p_i recorded σ_i, arriving at p_j before the marker) and post-snapshot messages (sent after p_i recorded σ_i, arriving at p_j after the marker).

• Impossible Orphan Message: Suppose p_i sends m after recording σ_i (so m follows 〈MARKER〉 on c_i,j). By FIFO ordering, p_j receives 〈MARKER〉 on c_i,j before receiving m. Upon receiving 〈MARKER〉, p_j records σ_j if it has not already done so; thus m is always received by p_j after p_j records σ_j, proving zero orphan messages.
• Precise In-Transit Capture: Any message m sent by p_i before σ_i (preceding the marker) that has not yet been received when p_j records σ_j (triggered by a marker from another channel c_k,j) arrives at p_j during the interval between σ_j and the arrival of the marker on c_i,j, and is therefore captured in Φ_i,j.

Across a strongly connected graph G = (P, C) with |P| = N vertices, |C| = E directed edges, and diameter D, every process sends 1 marker on each outgoing edge, yielding a total message complexity of O(E) = |C| marker messages and snapshot completion within O(D) max-hop message delays.

Reachability and Stable Predicate Detection

An important caveat analyzed by Chandy and Lamport is that the recorded global state S^* need not have occurred at any single physical instant during the actual execution e₁, e₂, ... Instead, Chandy and Lamport proved that if the snapshot starts in global state S_init and finishes in global state S_final, there exists a causally equivalent permutation of the execution's events—preserving every local process history and every happens-before dependency—that passes through S_init → S^* → S_final.

Consequently, the Chandy–Lamport snapshot is particularly suited for detecting stable properties—predicates P(S) that, once true in a system state S, remain true in all reachable future states S′ (such as distributed termination, deadlock, token loss, or unreferenced garbage objects):

• If P(S^*) is true in the recorded snapshot, then P(S_final) is guaranteed to be true when the snapshot finishes.
• If P(S^*) is false in the recorded snapshot, then P(S_init) was guaranteed to be false when the snapshot began.

In modern distributed stream processing engines such as Apache Flink, Asynchronous Barrier Snapshotting (ABS) (Carbone et al., 2015) adapts the Chandy–Lamport algorithm to directed acyclic dataflow graphs (DAGs): sources periodically inject checkpoint barriers (〈MARKER〉) into data streams, enabling precisely-once fault-tolerant state recovery across thousands of stateful operators without stopping high-throughput ingestion, complementing Byzantine fault tolerant replication and conflict-free replicated data type state stores.

What happens if communication channels are not FIFO?

If a channel c_i,j can reorder messages, a post-snapshot message m sent by p_i after 〈MARKER〉 could overtake 〈MARKER〉 in transit and arrive at p_j before p_j records σ_j, creating an orphan message and an inconsistent cut. For non-FIFO networks, the Lai–Yang algorithm (1987) replaces markers by coloring every process and its outgoing messages "white" (pre-snapshot) or "red" (post-snapshot); the first red message received by p_j triggers σ_j directly before processing that message, and channels are reconstructed by subtracting received white message counts from sent white message counts.

Why did the recorded global state S^* not necessarily exist at any single wall-clock time?

Suppose process p₁ records σ₁ at t = 10 ms and process p₂ (which exchanges no messages with p₁ between t = 10 ms and t = 50 ms) records σ₂ at t = 50 ms after executing several purely internal events. No single wall-clock instant simultaneously held (σ₁, σ₂), yet because the internal events at p₂ between 10 ms and 50 ms are causally concurrent with p₁'s snapshot, shifting them before t = 10 ms yields a valid causal execution that passes through S^*.

1. Chandy, K. M., & Lamport, L. (1985). "Distributed snapshots: Determining global states of distributed systems." ACM Transactions on Computer Systems, 3(1), 63–75. https://doi.org/10.1145/214451.214456
2. Lamport, L. (1978). "Time, clocks, and the ordering of events in a distributed system." Communications of the ACM, 21(7), 558–565. https://doi.org/10.1145/359545.359563
3. Lai, T. H., & Yang, T. H. (1987). "On distributed snapshots." Information Processing Letters, 25(3), 153–158. https://doi.org/10.1016/0020-0190(87)90125-690125-6)
4. Mattern, F. (1989). "Virtual time and global states of distributed systems." Proceedings of the International Workshop on Parallel and Distributed Algorithms, 215–226. https://doi.org/10.5555/646210.683629
5. Carbone, P., Fóra, G., Ewen, S., Haridi, S., & Tzoumas, K. (2015). "Lightweight asynchronous snapshots for distributed dataflows." arXiv Preprint / Apache Flink Foundation, arXiv:1506.08603. https://doi.org/10.48550/arXiv.1506.08603