Independent vs coordinated checkpointing; snapshot

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.