Global Snapshots: Consistent Cuts and the Chandy-Lamport Algorithm

Reading each server’s state is easy. Combining those readings into a state that makes sense is harder: a message may leave one server before its snapshot and reach another after its snapshot. A global snapshot must account for that message as well.

The Chandy-Lamport algorithm records a causally consistent global state while application messages continue flowing. Its central tool is a marker that defines a boundary on one channel.

1. Global state includes the network

Consider processes A and B with balances 100 and 50. A transfers 30 to B. In this teaching model, sending deducts 30 and receiving credits 30; the message carries the value between those events.

Recording only the middle row’s process states would report 120. Nothing disappeared: 30 belongs to the channel state. This is a message-passing model, rather than a prescription for implementing bank transfers.

flowchart LR
  A["A: recorded balance 70"] --> M["Channel A → B<br/>transfer 30 in transit"]
  M --> B["B: recorded balance 50"]
  A -.-> T["Global total: 70 + 30 + 50 = 150"]
  B -.-> T

Global state = every process’s local state + every channel’s in-transit messages. Synchronized clocks alone do not provide the missing channel information.

2. A consistent cut contains the causes of its events

A cut selects a prefix of events at each process. Different processes can stop at different positions in their local histories. An event before its process’s boundary is inside the cut; one after it is outside.

A cut C is consistent when:

e ∈ C and f → e imply f ∈ C

Here f → e means f happened before e in Lamport’s causal order. Including a receive therefore requires including its send. Each local history is already a prefix; message edges provide the essential cross-process condition.

Change the two cut positions below. An in-transit message preserves the total; a receive without its send produces an impossible combination. On a small screen, scroll the diagram horizontally to see both processes’ events.

A consistent cut need not match a moment on a shared wall clock. Concurrent events can be reordered without breaking causality; the cut describes a possible state in such an equivalent execution. It does not turn separately read values into a simultaneous physical measurement.

3. The assumptions behind the marker

The lecture’s basic model has a fixed set of processes and a directed channel in each direction between every pair. During a snapshot:

• Processes do not fail.
• Messages arrive intact, without loss or duplication, and are eventually delivered.
• Each channel is FIFO: its application messages and markers arrive in send order.
• A process can record its local state consistently with respect to its own events.
• We consider one run. Concurrent runs need distinct identifiers and separate recording state.

The key ordering rule is local: after recording its state, a process sends a marker on each outgoing channel before sending any later application message on that channel. Incoming-channel recording must also start before processing subsequent incoming messages. There must be no unrecorded gap at the boundary.

No global pause or synchronized clock is required. Capturing a local snapshot remains an implementation responsibility; allowing the application to continue does not make arbitrary concurrent reads atomic.

4. What each process does

The initiator saves its local state, sends outgoing markers, and records application messages on every incoming channel until that channel’s marker arrives.

For other processes, the first marker triggers the local snapshot and closes the channel on which it arrived.

flowchart TD
  M["Receive marker on channel c"] --> Q{"Local state already recorded?"}
  Q -->|No| S["Record local state"]
  S --> E["Record c as empty"]
  E --> O["Send outgoing markers before later app messages"]
  O --> R["Record app messages on other incoming channels"]
  Q -->|Yes| C["Close recording on c"]
  C --> K["Keep messages logged since the local snapshot"]

Why is the first-marker channel empty? FIFO ensures every application message sent before that marker has already arrived, so its effect is included in the just-recorded local state. Messages sent after the marker are outside the cut.

On other channels, the receiver has recorded its state but has not seen the sender’s boundary. Messages arriving in this interval belong in channel state. Record their contents while still processing them normally.

5. A complete three-process trace

Use a separate example: A = 100, B = 50, C = 0. Let C_BA denote B → A. A initiates; its marker to B is delayed. B sends a transfer m = 20 to A before B records its own state.

The table describes delivery order. Each process sends all outgoing markers when it records its local state, even if those markers arrive much later.

The result contains three local states and six channel states:

Local states:  S_A = 100, S_B = 30, S_C = 0
Channel state: C_BA = [transfer 20]; all other channels = []
Total:         100 + 30 + 0 + 20 = 150

The transfer physically arrives at step 3, yet remains in transit relative to the recorded cut: B’s snapshot includes its send, while A’s snapshot excludes its receive. Channel state describes the cut, not the network when recording finishes.

Later markers from other incoming channels are not duplicate network packets. Each closes a different channel. This example needs six markers, one per directed channel.

6. Why the cut is consistent

Suppose a receive were included but its send excluded. The sender would have recorded its state before sending that application message, so it must have sent a marker first. FIFO would deliver the marker first. The receiver would then save its state before receiving the application message, placing that receive outside the cut. This contradicts the assumption.

The argument extends along causal chains. Local prefixes preserve local order; markers prevent a cross-process effect from entering the cut without its cause. If an application message could overtake its earlier marker, this proof would fail. That is why the basic algorithm requires FIFO.

7. What the result can tell us

Snapshots support checkpointing and detection of stable predicates: conditions that, once true, remain true under the model’s allowed transitions. For a closed computation, termination requires both passive processes and no work messages in transit. Observing idle workers alone is insufficient.

Recording finishes when every process has saved its state and every incoming channel has been closed. A collector can then assemble the pieces; collecting them is separate from establishing consistency. With E directed channels, one run sends E markers, excluding collection traffic. Channel-log size depends on the application messages crossing the cut.

Snapshots alone do not provide durable recovery, atomic external side effects, or fault tolerance during recording. Those need additional protocols. Safety and Liveness explains which correctness claims a snapshot can support.

Check your understanding

1. Must every message received after a local snapshot be recorded? Only if the marker on its incoming channel has not arrived yet.
2. Can a later marker overwrite the local snapshot? No. Local state is recorded once per run; later markers close channels.
3. Does an empty channel snapshot mean the channel stayed physically empty? No. It means no application message crosses that channel’s boundary in the recorded cut.

Based on UIUC Cloud Computing Concepts, Part 1: “What is Global Snapshot?”, “Global Snapshot Algorithm”, and “Consistent Cuts” (slides and transcripts). Examples and diagrams are reconstructed for these notes.