--- title: "Independent vs coordinated checkpointing; snapshot" subject: "Distributed System" chapter: 9 key: "semester_7/distributed_system:independent-coordinated-snapshot" source: https://www.bctengineer.com/q/semester_7/distributed_system/independent-coordinated-snapshot site: BCT Engineering --- # Independent vs coordinated checkpointing; snapshot Distributed System · Chapter 9: Fault Tolerance - Asked in: 2074 Chaitra, 4+4 marks - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/independent-coordinated-snapshot - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-9 ## Question What are independent checkpointing and co-ordinated checkpointing? Explain snapshot algorithm used for backward recovery in distributed system. ## Short answer Independent checkpointing lets each process checkpoint alone, risking domino effect; coordinated checkpointing synchronizes processes so latest checkpoints are consistent, with no domino effect. The Chandy-Lamport snapshot algorithm uses markers on FIFO channels to record a consistent global state for backward recovery. ## Answer **Checkpointing** saves the state of a process (or of the whole distributed system) on stable storage so that it can be restored after a failure (backward recovery). In a distributed system the saved local states must form a **consistent global state** (a *distributed snapshot*): if the receipt of a message is recorded, its sending must be recorded too (no *orphan* messages). The most recent consistent set of checkpoints is the **recovery line**. #### Independent checkpointing Each process takes its checkpoints independently, without coordination. On recovery, the processes must find a consistent recovery line by tracing dependencies backwards. - It is simple and has no coordination overhead. - There is a risk of the **domino effect**: rolling back one process forces others to roll back, and so on, possibly to the initial state; many checkpoints must be kept, and finding a recovery line takes long. #### Coordinated checkpointing All processes synchronize so that their checkpoints together form a consistent global state, e.g. by a two-phase blocking protocol: 1. The coordinator sends *CHECKPOINT_REQUEST* to all processes. 2. Each process takes a local (tentative) checkpoint, stops sending application messages and acknowledges. 3. When the coordinator has all the acknowledgements, it sends *CHECKPOINT_DONE*; the processes make their checkpoints permanent and resume. - Only the latest checkpoint is needed, there is no domino effect, and recovery is simple. - Cost: coordination delay, and the processes are blocked for a while. **Snapshot algorithm (Chandy-Lamport)** gives a consistent global state without stopping the system. Channels are assumed to be FIFO. 1. The initiator records its own state, sends a **marker** on every outgoing channel, and starts recording the messages arriving on all its incoming channels. 2. A process receiving a marker for the first time (on any channel) records its own state, records that channel's state as empty, and sends markers on all its outgoing channels. It then starts recording the messages arriving on its other incoming channels. 3. When it later receives a marker on another incoming channel, it stops recording that channel; the messages recorded form that channel's state (the messages in transit). 4. When a marker has arrived on every incoming channel, the local snapshot is complete and is sent to the initiator, which assembles the global snapshot. The result is a consistent global state that is used for backward recovery after a failure. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which condition makes a set of local checkpoints a consistent global state? A. Every process checkpointed at exactly the same clock time B. If a message receipt is recorded, its sending is also recorded C. Every message sent is also recorded as received D. Only one process holds the checkpoint on stable storage Answer: B. Consistency means no orphan messages: any recorded receive must have its send recorded too. Messages recorded as sent but not received are simply in transit. (Key point: Consistent global state) 2. Why does independent checkpointing risk the domino effect? A. The coordinator crashes during the checkpoint B. Checkpoints are overwritten by newer ones C. Rolling back one process can force others to roll back, possibly to the initial state D. Messages are lost because channels are non-FIFO Answer: C. Uncoordinated checkpoints may not be mutually consistent, so dependencies force cascading rollbacks. (Key point: Domino effect) 3. In the two-phase blocking coordinated protocol, what happens after the coordinator receives all acknowledgements? A. It sends CHECKPOINT_DONE and processes make the checkpoint permanent and resume B. It asks every process to discard its tentative checkpoint C. It restarts all processes from the initial state D. It starts computing the recovery line Answer: A. Tentative checkpoints become permanent on CHECKPOINT_DONE, and processes resume sending application messages. (Key point: Coordinated checkpointing) 4. In Chandy-Lamport, what does a process do on receiving a marker for the first time on a channel? A. Stops all recording and discards its state B. Waits for markers on every channel before recording C. Records its own state, marks that channel empty, sends markers on all outgoing channels and records other incoming channels D. Sends its state to the initiator without sending markers Answer: C. First marker triggers local state recording, marker propagation and recording of messages on the other incoming channels. (Key point: Chandy-Lamport markers) ## Related in Distributed System - [Forward/backward recovery; checkpointing](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aforward-backward-coordinated-ckpt) — Distributed System, chapter 9 - [Short note: Forward and backward recovery](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aforward-backward-note) — Distributed System, chapter 9, asked 2× - [Avoiding faults; checkpointing compared](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aavoid-faults-checkpointing) — Distributed System, chapter 9 - [Distributed deadlock and recovery](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adistributed-deadlock-note) — Distributed System, chapter 8, asked 3× - [Autonomous vs distributed system](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aautonomous-vs-distributed) — Distributed System, chapter 1 - [K-fault tolerant system; recovery](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Ak-fault-recovery) — Distributed System, chapter 9 ## Related in other subjects - [Forward vs backward chaining](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aforward-vs-backward-chaining) — Artificial Intelligence, chapter 4, asked 3× - [Recovery from log: deferred vs immediate](https://www.bctengineer.com/question.md?key=semester_6%2Fdatabase_management_system%3Alog-recovery-deferred-immediate) — Database Management System, chapter 8