Implementing A Distributed Snapshot Algorithm: Chandy Lamport State Recording

2026-01-22 · Leonardo Benicio

Summary

A comprehensive technical exploration of implementing a distributed snapshot algorithm: chandy lamport state recording, covering key concepts, practical implementations, and real-world applications.

Contents

Introduction: Capturing the Ghost of a Distributed System

Imagine you’re the lead engineer for a global ride‑sharing platform. Your system consists of dozens of microservices—driver matching, pricing, payment, surge detection—each running across hundreds of servers in multiple data centers. One day, a subtle bug causes a driver to be charged twice for a cancellation. The logs show no error, but the payment service and the driver service seem to have seen a different order of events. How do you reconstruct the exact state of the entire system at the moment that driver tapped “cancel”? You can’t pause the system; drivers are still moving, rides are still being matched. You need a distributed snapshot—a consistent, global picture of the state of all processes and the messages in transit between them—taken without stopping the world.

This is not a hypothetical. Every large‑scale distributed system—from Amazon’s DynamoDB to Google’s Spanner, from financial trading platforms to streaming frameworks like Apache Flink—relies on snapshot algorithms for fault‑tolerance, debugging, and checkpointing. Without them, recovering from a crash would mean restarting from the beginning, losing all intermediate work. Detecting a deadlock across a web of microservices would be nearly impossible. Snapshots are the bedrock of reliability in distributed computing.

But taking a snapshot in a distributed system is surprisingly hard. In a single machine, you can simply stop the CPU and dump memory. In a distributed system, there is no global clock, no shared memory, and messages can be lost, duplicated, or still in flight when the snapshot begins. You need an algorithm that captures a consistent cut—a set of states where every event that happened before the cut is recorded, and every message that was sent but not yet received at the cut time is also accounted for. The challenge is to know what “happened before” means when processes run asynchronously.

This article will take you deep into the theory and practice of distributed snapshots. We’ll start by formalizing the problem, then introduce the landmark Chandy‑Lamport algorithm and its variants. We’ll examine real‑world implementations (Apache Flink, Kafka, Google Spanner) and discuss trade‑offs like snapshot size, performance, and recovery semantics. By the end, you’ll understand not only how to capture a ghost, but why that ghost is essential for building reliable distributed systems.

1. The Distributed Snapshot Problem – A Formal View

1.1 What Is a “Consistent Cut”?

A distributed system consists of a set of processes that communicate exclusively by sending messages over channels. Each process executes a sequence of events (send, receive, internal). The happened‑before relation ((\rightarrow)) between events captures causality: if event (a) happens before event (b) in the same process, or if (a) is the sending of a message and (b) its receipt, then (a \rightarrow b).

A cut is a set of events—one per process, marking the “last recorded event” in that process. A cut is consistent if no event that happens before a cut event is missing from the cut. More formally: if event (e) is in the cut and (f \rightarrow e), then (f) must also be in the cut. This ensures that no message whose sending is recorded has its corresponding receipt omitted (or vice versa).

1.2 The Snapshot Problem

The snapshot problem asks: given a set of processes that communicate asynchronously, can we record the local state of each process and the state of each channel (messages in transit) such that the resulting global state is consistent? The state must be captured without halting the distributed computation.

The difficulty arises because messages may be in flight when the snapshot begins. Suppose process (P1) sends a message to (P_2) just after (P_1) records its local state, but before (P_2) records its state. That message is “in the channel” from the snapshot’s perspective. The snapshot must record that message as part of the channel state. Conversely, if the message arrives _after (P_2) records its state, it should not be included.

1.3 Why Not Just Use Global Clocks?

In a single machine, we can pause all threads and dump memory. In a distributed system, there is no global shared memory or synchronous clock. Even with synchronized clocks (e.g., using NTP), the precision is limited. Moreover, the system may be too large to coordinate a simultaneous “stop” – and for many applications, stopping is simply not acceptable.

Thus we need non‑blocking snapshot algorithms that run concurrently with the application.

2. The Landmark: Chandy‑Lamport Algorithm (1985)

In 1985, K. Mani Chandy and Leslie Lamport published “Distributed Snapshots: Determining Global States of Distributed Systems.” Their algorithm remains the foundation for most practical snapshot implementations.

2.1 Assumptions

The communication channels are unidirectional, FIFO (first‑in‑first‑out), and reliable (no loss, no corruption, no duplication, but can have arbitrary delay).
Processes do not share clocks or memory.
Any process can initiate a snapshot.

2.2 Algorithm Intuition

The algorithm uses a special marker message. The marker acts as a “save point” in the channel. When a process receives a marker on a channel, it knows that all messages before that marker are part of the snapshot, and any messages after are not. The process must record its local state before it processes any marker.

There are two roles:

Initiator: A process that decides to take a snapshot records its own state, then sends a marker on every outgoing channel.
Non‑initiator: When a process receives a marker for the first time, it records its state, records the state of the incoming channel as empty, and sends markers on all outgoing channels. If it receives a marker later on another channel, it records the state of that channel as the sequence of messages received between the time it recorded its state and the receipt of that marker.

2.3 Step‑by‑Step Walkthrough

Consider a system with three processes: (P1), (P_2), (P_3). Channels are (C{12}), (C*{21}), (C*{23}), (C_{32}), etc.

(P_1) decides to take a snapshot.
(P_1) records its local state (S_1).
(P1) sends a marker on (C{12}) and (C_{13}).
The application messages continue to flow.

Now, suppose a message (m) from (P1) to (P_2) was sent before (P_1) sent the marker, but it’s still in transit. Because channels are FIFO, (m) arrives before the marker on (C{12}). So (P_2) will receive (m) first, then the marker.

(P2) receives the marker on (C{12}). Since this is the first marker (P2) has seen, it records its state (S_2) (including any messages it has processed so far). It sets the state of channel (C{12}) to empty (because all messages before the marker have already been received and processed). Then it sends markers on all outgoing channels (C*{21}) and (C*{23}).
Later, (P2) receives a marker from (P_3) on (C{32}). But (P2) already recorded its state. So it records the state of channel (C{32}) as the sequence of messages it received on that channel since it recorded its state, up to the moment the marker arrives. (If no message arrived, the channel state is empty.)

Similarly, (P_3) will receive markers and record its state when it first sees a marker.

After all processes have received a marker on all incoming channels, each process has its own local snapshot and the state of each incoming channel. The global snapshot is the union of all local states and channel states.

2.4 Example: Two‑Process System

Let’s illustrate with a concrete example. (P1) sends a message “100” to (P_2), then later sends a marker. (P_2) receives “100”, processes it, then receives the marker. The snapshot will include: state of (P_1) (say, after sending “100”), state of (P_2) (after processing “100”), and channel (C{12}) empty, channel (C_{21}) empty. Consistent? Yes. Now suppose (P_1) sends “200” after the marker. (P_2) receives “200” after recording its state, so “200” is not in the snapshot. That’s correct.

If we had the opposite ordering: (P1) sends marker before “100” (FIFO guarantees order), then (P_2) receives marker first, records its state (before seeing “100”). Then later “100” arrives. The snapshot would record channel (C{12}) containing message “100”. Consistent? Yes, because the sending of “100” happened before (P_2) recorded its state (since “100” was sent before the marker from (P_1)’s perspective, but due to FIFO the marker arrived first – this is possible only if the channel is non‑FIFO? Wait, our assumption is FIFO. Actually in a FIFO channel, if (P_1) sends marker then “100”, the marker must arrive first. So the scenario “marker then message” is the only possible if they are sent in that order. That’s fine. But if messages can overtake markers (non‑FIFO), the algorithm doesn’t work; that’s why FIFO is required.)

2.5 Why FIFO Matters

The Chandy‑Lamport algorithm relies on FIFO channels to guarantee that all messages sent before the marker on a channel are received before the marker. If a later‑sent message could overtake the marker, then a process might record its state after processing that later message, and the earlier message would still be in the channel. The snapshot could become inconsistent. Many real‑world systems (e.g., TCP) provide FIFO, so this assumption is reasonable.

2.6 Correctness Proof Sketch

The algorithm produces a consistent cut. We need to show that if event (e) happens before event (f) in the snapshot, then (e) is included. The key invariant: marker propagation ensures that the cut line moves forward in a way that respects causality. The proof is in the original paper; we’ll give an intuitive version:

Suppose a message (m) is sent after the sender’s snapshot. Then the marker is sent after (m) on the same outgoing channel (since marker is sent after state recording, and (m) is sent after state recording? Actually need careful: if process sends a message after recording its state, it must have sent the marker before? Wait, the algorithm: after recording state, the process sends markers on all outgoing channels. But it may still send application messages after recording state – those are not part of the snapshot. However, the marker was sent before any application messages that are sent after the snapshot? No, the marker is sent immediately after recording state, but application messages could be interleaved – the process can continue running. Since the marker is sent on the channel, and subsequent application messages are sent later, the marker will be earlier in the FIFO order. So any message sent after the snapshot on the same channel will come after the marker at the receiver. At the receiver, messages before the marker are processed before state recording; messages after are not. Thus the cut is consistent.

The formal proof uses induction on the causal chain.

3. Variants and Extensions

3.1 The Lai‑Yang Algorithm (Non‑FIFO Snapshots)

What if channels are not FIFO? For example, in an asynchronous system using UDP or multicast. The Lai‑Yang algorithm (1987) handles non‑FIFO channels by piggybacking snapshot information on every application message. Each message carries a “colour” (or a sequence number of the current snapshot). A process records its state when it first receives a message with a colour different from its own. This is more intrusive but works without FIFO.

3.2 Netzer‑Xu and Causal Consistency

Later work formalized the concept of causal consistency for snapshots. A snapshot is causally consistent if it respects the happened‑before relation. Netzer and Xu (1995) showed that the set of possible consistent cuts forms a lattice and introduced algorithms to find the “most recent” consistent snapshot after a failure.

3.3 Distributed Snapshots in Pregel‑like Systems

In graph‑processing frameworks like Pregel (BSP model), snapshots are easier because computation proceeds in supersteps where all processes synchronize. But many modern streaming systems (Flink, Kafka Streams) use asynchronous models and need sophisticated snapshot algorithms.

3.4 Global Snapshot vs. Local Checkpointing

An alternative to global snapshots is local checkpointing where each process independently saves its state and the system coordinates recovery using message logging. The classic “piecewise deterministic” (PWD) model (Elnozahy et al., 2002) uses optimistic message logging to avoid synchronizing all processes. However, for applications that require exactly‑once processing or global consistency (e.g., distributed databases), global snapshots are still preferred.

4. Real‑World Implementations and Use Cases

4.1 Apache Flink – Consistent Checkpoints for Stream Processing

Apache Flink is the poster child of snapshot‑based fault tolerance in streaming systems. It implements a variation of Chandy‑Lamport called asynchronous barrier snapshots.

Flink’s topology consists of sources, operators, and sinks connected by data streams.
At a checkpoint start, a “barrier” (marker) is injected by the source into the stream. Barriers flow downstream along each data path.
When an operator receives a barrier from all its input channels, it takes a snapshot of its state (e.g., keyed state, timers, pending records). It then emits the barrier on all output channels.
The state is stored in a durable backend (e.g., HDFS, S3).
Upon failure, Flink restarts all operators from the last successful checkpoint and replays the buffered data (if using exactly‑once semantics with transaction log).

Flink’s implementation handles multiple concurrent snapshots (only the latest is kept), non‑aligned checkpoints (to reduce latency), and unaligned checkpoints (for high‑throughput pipelines). The key difference from Chandy‑Lamport: Flink’s operators may have multiple input channels, and the barrier mechanism ensures that all inputs are aligned before taking the snapshot. This ensures a consistent cut across the entire directed acyclic graph.

Example: A Kafka source reads from two partitions. Barriers are injected into each partition. The operator must wait for both barriers before snapshotting. Meanwhile, data from partition 2 that arrives after its barrier is buffered but not processed (to maintain consistency). This can cause backpressure, which Flink mitigates with unaligned checkpoints.

4.2 Apache Kafka – Exactly‑Once Semantics via Transaction Logs

Kafka’s exactly‑once semantics rely on a combination of idempotent producers and transactional writes, which implicitly use a kind of snapshot: the transaction log records the “state” of transactions, and consumers read only committed messages. However, Kafka does not take global snapshots of all partitions. Instead, it uses a coordinator that marks a transaction as committed only after all writes are received. This is similar to a two‑phase commit, which itself is a snapshot of the transaction’s outcome.

4.3 Google Spanner – TrueTime and Snapshot Isolation

Google Spanner uses a global clock service called TrueTime to assign precise timestamps to transactions. This allows snapshot reads that are consistent without a centralized coordinator. Spanner does not use the Chandy‑Lamport algorithm per se, but its concept of “snapshot isolation” relies on timestamps that respect global time bounds. TrueTime’s hardware‑assisted clock synchronization provides a bound on clock uncertainty, enabling Spanner to safely choose a snapshot time without coordinating across all nodes.

4.4 Distributed Databases (CockroachDB, VoltDB)

CockroachDB uses a hybrid logical clock (HLC) to order transactions and supports snapshot isolation. For distributed transactions, it uses a transaction coordinator that gathers locks and performs a two‑phase commit. This is essentially a snapshot of the read/write sets at commit time. The consistency of the snapshot is guaranteed by the ordering of commit timestamps based on HLC.

4.5 Amazon DynamoDB – Incremental and Multi‑Master

DynamoDB does not use global snapshots for normal operations; it replicates data using quorums. However, for backup and restore, DynamoDB takes periodic snapshots across partitions, often using a similar marker‑based approach tailored for key‑value stores.

5. Practical Considerations and Trade‑offs

5.1 Snapshot Overhead

Taking a snapshot freezes the processing of some messages (e.g., waiting for barriers). This causes latency spikes. Many systems try to reduce overhead by taking snapshots asynchronously (e.g., Flink’s asynchronous snapshot capabilities), or by reducing frequency.

5.2 Snapshot Size

The state can be huge (e.g., millions of keys). To minimize storage cost, systems use incremental snapshots (saving only changes since last snapshot) or compression. Distributed snapshots of a large cluster can involve terrabytes of data; handling this efficiently is a research area.

5.3 Failure Recovery and Exactly‑Once Semantics

After a crash, the system restores from the last snapshot and replays any remaining logs. For exactly‑once processing, the log must be deterministic (e.g., sources support replay). In stream processing, this requires a durable source like Kafka with offsets, so that unprocessed messages can be re‑consumed.

5.4 Concurrent Snapshots

Some algorithms support multiple concurrent snapshots with different IDs. This can enable snapshots for different purposes (e.g., one for checkpoint, one for debugging). The Chandy‑Lamport algorithm can be extended by using multiple marker types.

5.5 Channel State Recording

In practice, the state of a channel can be large (many messages in flight). Systems often avoid explicitly recording channel state by using a global snapshot that aligns pipelining (like Flink’s barrier mechanism where channels are drained before snapshot). This is known as blocking vs. non‑blocking snapshots.

6. Formalization and Proof of Chandy‑Lamport

To cement understanding, we’ll go through a more rigorous description. Let the system be a directed graph where vertices are processes and edges are FIFO channels. A global state is a set of global states: ({ (si, c{ij}) }) where (si) is local state of (i) and (c{ij}) is a sequence of messages in transit from (i) to (j).

The algorithm is as follows (pseudocode for process (p)):

state[p] = nil
channel[p][*] = []   # list of messages recorded for each incoming channel
marker_received[p] = { false for each channel }

upon event InitiateSnapshot:
    state[p] = get_local_state()
    for each outgoing channel q:
        send marker to q

upon event Receive message m on channel in_p:
    if marker_received[in_p] == false:
        # process message normally
        ...
    else:
        # already recorded state; record channel state
        if state[p] is not nil:
            channel[p][in_p].append(m)

upon event Receive marker on channel in_p:
    if state[p] == nil:
        # first marker received
        state[p] = get_local_state()
        marker_received[in_p] = true
        channel[p][in_p] = []   # all messages before marker already processed
        for each outgoing channel q:
            send marker to q
    else:
        marker_received[in_p] = true
        # channel state already recorded from messages received after state recording

Termination: When every process has received a marker on all incoming channels (or equivalently, each process knows it has received markers on all channels – the algorithm usually uses a global termination detection like a coordinator). In practice, the initiator collects all states.

Example run with two processes (A) and (B), channels (A\rightarrow B) and (B\rightarrow A). Suppose initial states: (A) has counter=0, (B) has counter=100. (A) sends “inc” message to (B). Then (B) sends “dec” message to (A). Then (A) initiates snapshot:

(A) sets state=counter=0 after processing? Actually (A) should decide when to record. Let’s say (A) records state after sending “inc” but before receiving “dec”. State: counter=0? But (A) hasn’t done anything. More realistic: (A) has local variable x=5, sends “add 3” to (B). Then (B) receives it, adds 3, so B’s x=8. Then B sends “multiply 2” to A. A receives it, multiplies, x=10. Then A initiates snapshot. A’s state should be x=10. That would be consistent if we captured after processing. But the algorithm captures state at the moment of first marker receipt. Let’s simulate:

A initiates: record state (x=10), send marker on AB.
Meanwhile, B had already sent “multiply 2” but it hasn’t arrived at A yet? Actually B sent it after processing “add 3”. The message “multiply” is in transit.
A sends marker. The marker will travel on AB. Because FIFO, the order from A to B: if A had sent any message after marker? Not yet. So B will receive marker first on AB? B receives marker on AB: first marker, so B records its state (x=8? Actually B’s state after processing “add 3” is x=8, before sending any response). B then sends markers on all outgoing (BA). Now, the “multiply 2” message from B to A was already sent before B’s marker on BA? Yes, because B sent “multiply” earlier. So on channel BA, the message “multiply” is in transit. But the marker from B to A will be sent after B records state, so it’s later in FIFO order. So A will receive “multiply” first, then marker. When A receives “multiply” after it already recorded state (initiate snapshot), but before receiving marker from B? Actually A has already recorded state (x=10). When it receives “multiply” on BA, since it hasn’t received marker on BA yet, it will process it normally? Wait, algorithm says: upon receiving a message on channel in_p, if marker_received[in_p] is false, process normally. Here marker_received[BA] is false (only marker on AB was received? Actually A hasn’t received any marker on BA yet). So A will process “multiply”, updating its state to x*2=20. Then later A receives marker on BA, and then records channel BA as empty (since state not nil, but mark already? Actually it will set marker_received[BA]=true and since it already recorded state, it will start logging subsequent messages on BA? But there are none. The channel state will be empty because the only message “multiply” was already processed before the marker. That means the snapshot will miss the fact that “multiply” was in transit? Let’s analyze consistency: The snapshot records A’s state as x=20? No, because A’s state was recorded at the beginning as x=10. But then it processed “multiply” afterwards. The recorded state x=10 is inconsistent with the fact that “multiply” was sent before B’s marker. According to the algorithm, when A first recorded its state (initiate), it set state[A]=10. That state is frozen. When later a message arrives on a channel before the marker, if marker_received[channel] is false, the process continues to process it normally, but the state that was recorded is unchanged. The process’s actual state changes, but the snapshot still holds the old state. So the snapshot state of A is 10. The channel BA will record “multiply” as part of channel state? Let’s see: When A receives marker on BA, it sets marker_received[BA]=true. Since its state is already recorded (non‑nil), it records the channel state as the sequence of messages received on that channel since it recorded its state up to the marker. But those messages are those received after state recording but before marker receipt. The message “multiply” was received before marker, but marker_received[BA] was false at that time. The algorithm does not automatically buffer messages that arrive before the marker if the state was already recorded. Actually the algorithm as defined above requires that after state is recorded, if a message arrives on a channel where marker not yet received, it is processed normally (i.e., changes the live state). It is *not* added to the channel state because the channel state is recorded only when the marker arrives. But then the channel state would miss that message because it was already processed. This is a bug in my pseudocode – let’s correct.

In Chandy‑Lamport, after a process records its state, it must stop processing messages on channels where the marker has not yet arrived? No, that would block. The algorithm actually allows a process to continue processing messages after recording its state, but it must ensure that the messages that arrive on a channel before the marker are recorded as part of that channel’s state. So we need to buffer them. The standard description: After recording its state, for each incoming channel, the process needs to record all messages that arrive on that channel until it receives a marker on that channel. Those messages are the channel state. So the process should not process them normally; it just appends them to the channel state buffer. Meanwhile, the process can still send messages and process internal events, but it cannot process messages from a channel whose marker hasn’t arrived because those messages would be part of the snapshot channel state. In effect, the process blocks processing of messages on that channel until the marker arrives? That would cause deadlock. But in the original algorithm, the process can continue processing messages from channels where it has already received the marker – those messages are post‑marker and not part of the snapshot. For channels awaiting marker, the process either buffers them (adding to channel state) and does not process them until after snapshot? Actually the literature often says that after recording its state, the process begins to record all incoming messages on a channel until it receives a marker on that channel. The process does not process those messages; it simply saves them. This is fine because the process’s logical execution can continue: it can still send messages and perform internal actions. The buffering of incoming messages creates a temporary backlog, but the process is not blocked from sending. Once the marker arrives, it stops recording that channel and can then process the buffered messages (which are now part of the snapshot channel state, not current process state). However, that would mean the process’s live state after the snapshot does not include those buffered messages. This is consistent: the snapshot captures a state just before those messages were processed.

Let’s revisit our example with correct behavior:

A initiates: records state (x=10). Sends marker on AB.
A sets a flag: for each incoming channel, start a list. For channel BA, list is empty.
A continues execution. It can send messages but not process any incoming from BA until marker received.
Meanwhile, B receives marker on AB (first marker). B records state (x=8). Sends marker on BA. B now records for its incoming channels: on AB, it already received marker, so no recording needed? Actually B’s state recording is done; it will start recording messages on other incoming channels until marker arrives. But since AB marker came first, B’s channel AB state is empty. B may process messages normally? After recording state, B can process messages from channels where marker received? For AB, yes. But B also will receive messages on other channels? Only one channel BA outgoing from B, but incoming from A? Actually B has incoming channel AB – already marker received, so no recording. So B can resume normal processing. B may send more messages.
Now back to A: A receives message “multiply” on BA. But marker on BA has not yet arrived, so A appends “multiply” to its list for channel BA. It does not process it. Then eventually A receives marker on BA. Upon receipt, A stops recording BA (channel state list = [“multiply”]), and marks marker_received[BA]=true. Now A can process the buffered messages if needed? But the snapshot is already taken; the current live state of A after snapshot continues from before processing “multiply”. So after snapshot, A’s live state is still x=10, but the buffered message “multiply” is considered part of the snapshot channel state. The global snapshot will have A’s state = 10, B’s state = 8, channel BA = [“multiply”], channel AB = []. Is this consistent? Let’s check causality: The sending of “multiply” happened at B: after B’s state record? Actually B sent “multiply” before recording its state (because B’s state recording occurred after B sent that message? In our scenario, B sent “multiply” before receiving marker from A? Let’s order:

A sends “add 3” to B (time t1)
B receives “add 3”, updates x to 8, sends “multiply 2” to A (t2)
A receives “multiply 2”? Actually A initiates snapshot before receiving that? In our scenario, A initiated after receiving “multiply”? Let’s set a timeline:

We need to be precise. Let’s define event chronology with physical time (even though no global clock, but for reasoning):

time 0: A x=5
time 1: A sends “add 3” to B (message m1)
time 2: B receives m1, processes: x=5+3=8, then sends “multiply 2” to A (message m2)
time 3: A initiates snapshot. At that moment, A has not yet received m2 (still in transit). A records local state: x=5? Wait, after sending m1, A hasn’t done anything else. So A’s state at time 3 is still x=5? But earlier we assumed A processed m2? Let’s correct: Suppose A had processed m2 before snapshot? Actually in our initial story, A after receiving m2 would have x=10. But we need to decide. Let’s simplify: A’s state is x=5, B’s state after processing m1 is x=8. Then A initiates snapshot. So A records x=5. Then A sends marker on AB.
time 4: B receives marker on AB. B records state: x=8 (since m1 processed). B sends marker on BA.
time 5: A receives m2 on BA. Since marker not yet arrived, A buffers m2.
time 6: A receives marker on BA from B. A stops buffering BA, so channel state BA = [m2]. Now global snapshot: A state x=5, B state x=8, channel BA contains m2. This is consistent because message m2 was sent by B (event at time 2) and is still in transit at the cut (since A hasn’t processed it). The cut includes that send event (since B’s recorded state is after sending m2) and includes the receipt? No, the receipt event (process m2) is not included because if it were included, we would need m2 to be not in channel. But here A’s recorded state did not include processing m2. So the send is in the cut, the receive is not, so m2 is correctly recorded as in transit. Consistency holds.

Now what about the message m1? Its send (by A at time 1) is part of A’s recorded state (since A recorded state after sending?), Actually A recorded x=5 after sending m1? If A sent m1 at time 1, then at time 3 A’s state is still x=5, but the action of sending m1 is already done. The recorded state includes the fact that m1 was sent? Local state is just variables, not message history. But we need to ensure that the cut captures the fact that m1 was already received by B. B’s recorded state includes processing m1 (x=8), so that’s consistent. The channel AB is empty. So everything is consistent.

The algorithm works.

Important: In real implementations like Flink, operators do buffer incoming messages on channels that have not yet received a barrier. That’s why flink “aligned checkpoints” can cause backpressure: the operator pauses processing on fast channels while waiting for slow ones.

7. Alternatives and Recent Advances

7.1 Lightweight Snapshot Algorithms for Causal Logs

In systems like Apache Cassandra, the CDC (Change Data Capture) approach uses a logical clock to assign sequence numbers to writes. A snapshot can be taken by recording all writes with sequence number <= some threshold. This doesn’t require markers but requires a global counter that is monotonic.

7.2 State Machine Replication and Raft

In consensus algorithms like Raft, the leader takes snapshots of its log to reduce storage. The snapshot is taken locally; followers catch up by installing the snapshot. This is a simpler case because there is only one leader at a time. However, Raft also supports membership changes, which require a form of joint consensus, but not distributed snapshots.

7.3 Approximate Snapshots and Probabilistic Methods

For debugging and monitoring, sometimes an exact consistent cut is not needed. “Causal tracing” tools (e.g., Dapper, Zipkin) sample a fraction of requests and reconstruct causal paths. These are not snapshots of overall state but allow root‑cause analysis.

7.4 Using Vector Clocks for Snapshot

Vector clocks can be used to determine if two events are concurrent. A snapshot can be defined as a set of vector clocks that form a consistent cut. The algorithm can be: each process records its state along with its vector clock. Then a global snapshot is consistent if for every pair of events, the vector clocks are not contradicting. This is more of a validation than a capture algorithm.

7.5 Checkpointing in Serverless and FaaS

Function‑as‑a‑Service platforms (AWS Lambda, Azure Functions) are stateless by default, but stateful extensions (e.g., Durable Functions, Cloudflare Workers) often rely on exactly‑once processing by recording state to external storage. Snapshots are taken per‑function instance, not across the entire system.

8. Code Example: Simple Distributed Snapshot Emulation

We can illustrate the Chandy‑Lamport algorithm with a small Python simulation. (Note: This is simplified and runs in a single process for demonstration.)

import threading
import queue
import time
import random

class Process:
    def __init__(self, pid, channels_out, channels_in, initial_state):
        self.pid = pid
        self.state = initial_state
        self.channels_out = channels_out  # dict: target -> queue
        self.channels_in = channels_in    # dict: source -> queue
        self.snapshot_state = None
        self.marker_received = {src: False for src in channels_in}
        self.channel_states = {src: [] for src in channels_in}
        self.recording = False

    def send_message(self, target, msg):
        self.channels_out[target].put(msg)

    def send_marker(self):
        for target in self.channels_out:
            self.channels_out[target].put(('MARKER', self.pid))

    def run(self, snapshot_initiator=False):
        if snapshot_initiator:
            self.initiate_snapshot()
        while True:
            # non‑blocking check for incoming messages
            for src, q in self.channels_in.items():
                if not q.empty():
                    msg = q.get()
                    self.handle_message(src, msg)

    def handle_message(self, src, msg):
        if isinstance(msg, tuple) and msg[0] == 'MARKER':
            self.handle_marker(src)
        else:
            if self.marker_received[src]:
                # Already have marker on this channel, so this message is after marker
                # In real algorithm, these are not part of snapshot
                # Here we just process normally (process state may change, but snapshot unchanged)
                self.state = self.process_message(msg)
            else:
                if self.recording:
                    # We have recorded state, but not yet marker on this channel
                    # Appending to channel state (as per algorithm)
                    self.channel_states[src].append(msg)
                else:
                    # Haven't recorded state yet, normal processing
                    self.state = self.process_message(msg)

    def handle_marker(self, src):
        if self.snapshot_state is None:
            # First marker received
            self.snapshot_state = self.state.copy() if isinstance(self.state, dict) else self.state
            self.recording = True
            self.marker_received[src] = True
            self.channel_states[src] = []  # all messages before marker already processed
            # Send markers to all outgoing channels
            self.send_marker()
        else:
            self.marker_received[src] = True
            # Channel state already built from messages recorded since snapshot start

    def initiate_snapshot(self):
        self.snapshot_state = self.state.copy() if isinstance(self.state, dict) else self.state
        self.recording = True
        self.send_marker()
        # No marker_received set yet

    def process_message(self, msg):
        # Application‑specific processing
        print(f"Process {self.pid} processing message {msg}")
        return self.state  # placeholder

# Example usage
if __name__ == "__main__":
    q_ab = queue.Queue()
    q_ba = queue.Queue()
    p_a = Process('A', {'B': q_ab}, {'B': q_ba}, {'x': 5})
    p_b = Process('B', {'A': q_ba}, {'A': q_ab}, {'x': 0})
    # Run with threads (simplified)
    import threading
    t_a = threading.Thread(target=p_a.run, args=(True,))
    t_b = threading.Thread(target=p_b.run)
    t_a.start()
    t_b.start()
    # Send a message from A to B
    p_a.send_message('B', 'add 3')
    time.sleep(0.1)
    print("Snapshot A:", p_a.snapshot_state)
    print("Snapshot B:", p_b.snapshot_state)
    print("Channel state A->B:", p_a.channel_states.get('B'), p_b.channel_states.get('A'))

This simulation is crude (no proper termination, no message ordering). But it demonstrates the core logic.

9. Conclusion: The Ghost is Captured

We started with a ride‑sharing bug and the need to capture a ghostly global state. The Chandy‑Lamport algorithm provides an elegant, non‑blocking solution that works under realistic assumptions. From stream processing engines like Flink to transactional databases, the idea of markers, barriers, and consistent cuts is woven into the fabric of reliable distributed design.

But the story doesn’t end here. Modern systems push the boundaries with ultra‑low latency, massive scale, and mutable state. Researchers continue to develop snapshot algorithms that are faster, smaller, and more resilient. For instance, Minimizing Snapshot Overhead using Unaligned Checkpoints (Flink), Deterministic Snapshots in Multi‑Core Systems, and Blockchain‑based Global States are active research areas.

If you’re building a distributed system today, consider where your snapshots are. Are they consistent? Can you answer “What is the state of the system at this exact point?” without stopping the world? If not, you may one day be staring at logs, trying to understand why a driver got charged twice. With the right snapshot algorithm, you can capture that ghost and bring order to chaos.