Process A initiates a snapshot, records its state, and sends markers. Before receiving A's marker, Process B sends a $50 transfer to A. A later receives this $50 message before B's marker arrives on that channel. How should A handle this $50 message?
AIgnore it — A has already recorded its state, so messages arriving afterward are excluded from the snapshot
BRecord it as part of A's channel state — it is an in-flight message that was in transit at snapshot time
CDiscard it — only the initiating process records in-flight messages
DInclude it in the snapshot unconditionally, regardless of when it was sent
After recording its own local state, A begins buffering messages arriving on channels from which it has not yet received a marker. The $50 transfer arrived after A took its snapshot but before B's marker arrived on that channel — meaning the transfer was logically 'in-flight' at snapshot time. FIFO guarantees that B sent this message before sending its marker, so the message is a pre-snapshot event and must be included in the channel state to produce a consistent snapshot.
Question 2 Multiple Choice
Why does the Chandy-Lamport algorithm require FIFO (first-in-first-out) communication channels?
ATo ensure that the initiating process sends markers before any regular messages during the snapshot
BTo guarantee that all messages sent before a marker on a given channel arrive at the receiver before that marker does
CTo prevent any process from recording its state more than once during a single snapshot
DTo ensure that marker messages travel faster than regular application messages
FIFO is essential for correctness. When a process receives a marker on a channel, it stops recording messages on that channel — assuming all pre-snapshot messages have already arrived. This assumption is only valid if channels are FIFO: if a message sent before the marker can arrive after it, the process would miss recording that pre-snapshot message, breaking the consistency of the cut. Without FIFO, a more complex protocol is required.
Question 3 True / False
The Chandy-Lamport snapshot captures the global state of a distributed system at a single physical instant in time.
TTrue
FFalse
Answer: False
This is the central misconception about distributed snapshots. There is no global clock in a distributed system — 'physical simultaneity' is meaningless across separate processes. The Chandy-Lamport snapshot instead captures a consistent cut: a division of all events into 'before' and 'after' the snapshot such that no 'after' event causally precedes a 'before' event. This logical consistency is sufficient for verifying global invariants, even though different processes record their state at different physical times.
Question 4 True / False
When a process receives a marker message for the first time, it immediately records its own local state before forwarding markers to its neighbors.
TTrue
FFalse
Answer: True
This is a critical rule of the algorithm. The process must record its state at the moment it first receives a marker — before any other actions — to ensure that state is captured before further messages can change it. It then sends markers on all outgoing channels and begins buffering messages on channels from which it has not yet received a marker. The order matters: record state, then propagate markers.
Question 5 Short Answer
What does 'consistent cut' mean in the Chandy-Lamport algorithm, and why is consistency sufficient for verifying global invariants even without physical simultaneity?
Think about your answer, then reveal below.
Model answer: A consistent cut divides all events into 'before the snapshot' and 'after the snapshot' such that if an event is in the 'after' set, none of its causal predecessors are in the 'before' set. This means the snapshot represents a state the system could have occupied — it is causally coherent. Global invariants like 'total money is conserved' must hold at every causally consistent state, so verifying them against a consistent snapshot is valid even though different processes recorded their state at different physical moments.
The key insight is that consistency is a logical property, not a temporal one. In a distributed system, causal ordering is the fundamental structure, not clock time. The Chandy-Lamport snapshot respects causal ordering because the marker barriers ensure each process records its state after all causally prior events have been processed. Any invariant that holds at every reachable system state will hold at a consistent snapshot — which is precisely what makes the algorithm practically useful for debugging, checkpointing, and verification.