Chandy-Lamport Algorithm: Capturing Consistent Global State in Distributed Systems

In a centralized system, capturing a snapshot for checkpointing or debugging simply requires freezing the execution thread and dumping memory and disk registers. In a distributed system with dozens or thousands of nodes communicating asynchronously over non-deterministic networks, there is no shared memory, no synchronized physical clock, and no way to freeze all nodes simultaneously without causing severe system outages.

Formulated by K. Mani Chandy and Leslie Lamport in 1985, the **Chandy-Lamport Algorithm** captures a globally consistent state snapshot across all nodes and in-flight network communication channels without halting normal transaction processing ('non-blocking global snapshot').

Theoretical Foundations: The Concept of a Consistent Cut

A global state consists of two parts: the local internal state of every process $P_i$ and the state of every directed communication channel $C_{ij}$ connecting process $i$ to process $j$.

Consistent Cut Invariant

A cut represents a partition of the distributed timeline into 'past' (included in the snapshot) and 'future' (excluded from the snapshot). A cut is mathematically **consistent** if and only if:

An inconsistent cut occurs if a snapshot records the receipt of a message without recording the corresponding send event—effectively capturing an effect without its cause.

The Marker Propagation Rules

The algorithm assumes channels are unidirectional, reliable, and strictly follow FIFO (First-In, First-Out) delivery ordering. Special control messages called **Markers** coordinate the snapshot alongside regular application messages.

1. Snapshot Initiation (By any arbitrary process $P_i$)

1. Process $P_i$ records its own local state.
2. Before sending any further regular messages, $P_i$ sends a `Marker` along all of its outgoing communication channels.
3. $P_i$ immediately starts recording all incoming messages on all incoming channels $C_{ki}$.

2. Receiving a Marker (Process $P_j$ receives Marker along channel $C_{ij}$)

• Case A (First Marker Seen by $P_j$): If $P_j$ has not yet recorded its local state, it immediately saves its local state, marks channel $C_{ij}$ as empty (no in-flight messages between the marker and the snapshot), sends a `Marker` along all its outgoing channels, and begins recording incoming messages on all other incoming channels $C_{kj}$ ($k \neq i$).
• Case B (Subsequent Marker Seen by $P_j$): If $P_j$ has already recorded its local state, it stops recording incoming messages on channel $C_{ij}$. The captured state of channel $C_{ij}$ is precisely the sequence of messages received on $C_{ij}$ between the moment $P_j$ recorded its state and the moment the Marker arrived.

3. Termination

The algorithm finishes locally for process $P_j$ once it has received a `Marker` on every one of its incoming channels. Once all processes finish, the combined local states and channel message queues represent a globally consistent snapshot.

C++ Conceptual Simulation Blueprint

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

struct Message {
    bool isMarker;
    std::string senderId;
    std::string payload;
};

class SnapshotProcess {
private:
    std::string id;
    int localBalance; // Example internal state
    bool stateRecorded = false;
    std::unordered_map<std::string, bool> channelRecording;
    std::unordered_map<std::string, std::vector<Message>> inFlightChannels;
    std::vector<std::string> incomingChannels;

public:
    SnapshotProcess(std::string processId, int initialBalance, std::vector<std::string> inChannels)
        : id(processId), localBalance(initialBalance), incomingChannels(inChannels) {}

    void initiateSnapshot() {
        recordLocalState();
        // Broadcast Marker to all outgoing channels in runtime
    }

    void recordLocalState() {
        stateRecorded = true;
        // Local state captured
        for (const auto& ch : incomingChannels) {
            channelRecording[ch] = true;
        }
    }

    void handleIncomingMessage(const std::string& fromChannel, const Message& msg) {
        if (msg.isMarker) {
            if (!stateRecorded) {
                recordLocalState();
                channelRecording[fromChannel] = false; // Empty channel for first marker
            } else {
                // Stop recording for this specific channel
                channelRecording[fromChannel] = false;
            }
        } else {
            if (stateRecorded && channelRecording[fromChannel]) {
                // In-flight message received after state record, before marker -> buffer it
                inFlightChannels[fromChannel].push_back(msg);
            }
            // Process regular application payload
            localBalance += std::stoi(msg.payload);
        }
    }
};

Real-World Engineering and Production Implementations

1. Distributed Stream Processors (Apache Flink): Implements the Asynchronous Barrier Snapshotting (ABS) variant of Chandy-Lamport, injecting checkpoint barriers into data streams to achieve exactly-once processing guarantees without stopping message pipelines.
2. Distributed Deadlock Detection: Capturing global wait-for graphs across distributed lock managers to identify multi-node circular wait deadlocks.
3. Distributed Database Garbage Collection & Archival: Freezing consistent baseline checkpoints for point-in-time recovery (PITR) and log pruning in scale-out data platforms.
4. Distributed System Debugging: Exporting globally valid post-mortem state dumps to reproduce transient non-deterministic concurrency bugs offline.