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.
Do you like what you are reading? Subscribe to receive updates.
Unsubscribe anytime