Snapshot Algorithm Of Chandy And Lamport

9 min read

The Chandy-Lamport snapshot algorithm stands as a cornerstone in the field of distributed systems, providing an elegant solution to a deceptively difficult problem: how to capture a consistent global state of a distributed system without stopping the entire computation. In a world where processes operate concurrently across different nodes, communicating solely through message passing, the concept of "now" is ambiguous. Consider this: physical clocks drift, network latency varies, and there is no shared memory to inspect. This algorithm, introduced by K. Mani Chandy and Leslie Lamport in 1985, allows a process to initiate a distributed snapshot that records the local state of every process and the state of every communication channel, guaranteeing that the resulting picture represents a state that could have occurred during the actual execution.

The Core Challenge: Global State in a Distributed World

Before diving into the mechanics, it is essential to understand why a simple "stop-the-world" approach fails in distributed environments. Now, in a centralized system, a debugger can pause the CPU, dump the registers, memory, and stack, and analyze the state at leisure. In a distributed system, processes are physically separated. Asking every process to "freeze and report your state right now" is impossible because "right now" does not exist globally. Consider this: messages are in flight—sent by one process but not yet received by another. If Process A records its state after sending a message, but Process B records its state before receiving that same message, the global snapshot becomes inconsistent: the message appears to have vanished into thin air.

A consistent global state must satisfy a specific condition: for any message recorded as received in the snapshot, the corresponding send event must also be recorded in the snapshot. The Chandy-Lamport algorithm achieves this consistency without requiring synchronized clocks or halting the underlying application.

System Model and Assumptions

The algorithm operates under a standard set of assumptions that define the system model:

  • Processes and Channels: The system consists of a finite set of processes connected by directed, unidirectional communication channels.
  • Reliable FIFO Channels: Channels are assumed to be reliable (no message loss, duplication, or corruption) and First-In-First-Out (messages arrive in the order sent).
  • No Shared Memory: Processes communicate exclusively via message passing.
  • Arbitrary Delays: Message transmission delays are finite but unpredictable.
  • Marker Messages: The algorithm introduces a special control message type called a marker, distinct from application messages.

These assumptions are theoretical ideals. In practice, implementations often relax the FIFO requirement using sequence numbers, but the core logic remains solid Easy to understand, harder to ignore..

The Algorithm: Step-by-Step Mechanics

The beauty of the Chandy-Lamport algorithm lies in its simplicity. Any process can act as the initiator at any time. On top of that, it requires no central coordinator after initiation. The algorithm defines two distinct sets of rules: one for the initiator and one for all other processes receiving a marker for the first time.

1. Initiator Rules (Starting the Snapshot)

When a process $P_i$ decides to take a snapshot, it executes the following atomic actions:

  1. Record Local State: $P_i$ saves its own local state (variables, program counter, stack, etc.) to stable storage.
  2. Send Markers: $P_i$ sends a marker message along all its outgoing channels before sending any further application messages on those channels.

This effectively draws a line in the sand for the initiator: everything before the marker send is "past," everything after is "future."

2. Receiver Rules (Propagating the Snapshot)

When a process $P_j$ receives a marker on channel $C$ from process $P_k$, two scenarios arise depending on whether $P_j$ has already recorded its state for this snapshot And it works..

Case A: First Marker Received ($P_j$ has not recorded state)

This is the critical propagation step.

  1. Record Local State: $P_j$ immediately records its own local state.
  2. Record Channel State (Incoming): The state of the incoming channel $C$ is recorded as empty. Why? Because $P_j$ records its state upon receipt of the marker. Since channels are FIFO, any application message sent by $P_k$ before the marker must have arrived before this marker. Which means, no "in-transit" messages exist on $C$ that were sent before the snapshot cut.
  3. Send Markers: $P_j$ sends a marker on all its outgoing channels before sending any further application messages.

Case B: Subsequent Marker Received ($P_j$ has already recorded state)

  1. Record Channel State (Incoming): The state of channel $C$ is recorded as the sequence of application messages received on $C$ since $P_j$ recorded its local state up until this marker arrived.
    • Reasoning: $P_j$ recorded its state at some point in the past (triggered by a marker on a different channel). Any application message arriving on $C$ after that recording but before this marker represents a message that was "in transit" at the moment the global snapshot cut occurred. The sender ($P_k$) had not yet sent its marker (otherwise $P_j$ would have received it earlier), meaning $P_k$ recorded its state after sending this application message. Thus, the message is "sent but not received" relative to the snapshot cut.

3. Termination

The algorithm terminates naturally. Because the network graph is finite and markers are forwarded along every outgoing edge exactly once per snapshot initiation, the wave of markers eventually reaches every process. Once a process has received a marker on all its incoming channels, its participation in that specific snapshot is complete. The collected local states and channel states are then typically sent to a designated collector process for assembly.

You'll probably want to bookmark this section The details matter here..

A Concrete Walkthrough: Visualizing the "Cut"

Imagine three processes: $P_1$, $P_2$, $P_3$. Channels: $P_1 \to P_2$, $P_2 \to P_3$, $P_1 \to P_3$.

  1. $P_1$ Initiates: $P_1$ records State $S_1$. Sends Marker $M$ on $P_1 \to P_2$ and $P_1 \to P_3$.
  2. $P_2$ Receives $M$ (First time): $P_2$ records State $S_2$. Records Channel $P_1 \to P_2$ as Empty. Sends Marker $M$ on $P_2 \to P_3$.
  3. $P_3$ Receives $M$ from $P_1$ (First time): $P_3$ records State $S_3$. Records Channel $P_1 \to P_3$ as Empty. Sends Markers on outgoing channels (none in this example).
  4. $P_3$ Receives $M$ from $P_2$ (Second time): $P_3$ has already recorded state. It records Channel $P_2 \to P_3$ state as: All application messages received on this channel since Step 3.

Why is this consistent? Consider an application message $m$ sent $P_2 \to P_3$ Small thing, real impact..

  • If $m$ arrived at $P_3$ before Step 3: It is part of $S_3$. Channel state is empty. Consistent (Received & Send recorded).
  • If $m$ arrived at $P_3$ between Step 3 and Step 4: It is not in $S_3$. It is recorded in Channel $P_2 \to P_3$ state. $P_2$ sent $m$ before sending its Marker (Step 2), so $

Ensuring a Consistent Global State

The algorithm's true power lies in its guarantee that the combination of recorded local states and channel states forms a consistent global snapshot. In distributed systems, consistency means that the snapshot reflects a single, coherent moment in time, even though events occur asynchronously. Specifically, the snapshot must satisfy two conditions:

  1. No Message is Lost or Duplicated: Every application message sent by a process before it recorded its state is accounted for. It is either included in the receiver's recorded state (if received before the receiver recorded) or in the recorded channel state (if in transit during the cut). There is no double-counting because the algorithm's rules create a clear boundary: the marker acts as a "cut line." Messages sent before the sender's marker are considered part of the "past" of the snapshot, while messages sent after are part of the "future."

  2. Causality is Preserved: If a message $m$ is recorded as part of a channel state from $P_k$ to $P_j$, then $P_k

Just Added

Just Hit the Blog

Neighboring Topics

More to Discover

Thank you for reading about Snapshot Algorithm Of Chandy And Lamport. We hope the information has been useful. Feel free to contact us if you have any questions. See you next time — don't forget to bookmark!
⌂ Back to Home