Distributed Snapshots: Determining Global States of Distributed Systems

A distributed snapshot records a system’s global state while it continues running, without requiring a shared clock. It captures:

Each process’s local state.

Messages currently in transit on communication channels.

Consistent snapshot

The snapshot must form a consistent cut:

If it contains a message’s receipt, it must also contain its send.

It may contain a send without its receipt; that message is recorded as in transit.

Chandy–Lamport algorithm

The initiating process records its local state.

It sends a special marker on every outgoing channel before sending more application messages.

When another process receives its first marker, it:

Records its local state.

Records that incoming channel as empty.

Sends markers on all outgoing channels.

Records messages arriving on its other incoming channels.

When a marker arrives on one of those other channels, recording for that channel stops. The recorded messages constitute its in-transit state.

The snapshot completes after every process receives markers on all incoming channels.

Assumptions

The classic algorithm assumes:

Reliable, FIFO channels.

No process or channel failures during capture.

Markers are distinguishable from regular messages.

No synchronized clocks are required.

Why it works

FIFO ordering makes each marker a boundary between messages sent before and after the snapshot. Messages crossing that boundary are correctly classified as in transit, producing a consistent global state—even though that state may never have existed at one exact wall-clock instant.

Typical applications include checkpointing, failure recovery, termination detection, and deadlock detection.