Forward/backward recovery; checkpointing

Backward recovery

The system is brought back to a previously saved correct state (a recovery point or checkpoint) and execution resumes from there. The state is recorded periodically by checkpointing and/or message logging. It is general-purpose and does not need to know which error occurred, but it has overhead (saving state), it loses the work done since the checkpoint, and it is impossible for some operations (e.g. once a cash dispenser has paid out money, that cannot be undone). Example: restoring a database from a checkpoint and replaying the log.

Forward recovery

The system moves to a new correct state from which it can continue, by correcting the error without going back. It requires knowing in advance which errors may occur. Examples: error-correcting codes, and erasure correction, where a lost packet is reconstructed from other, successfully delivered packets instead of being resent.

Coordinated checkpointing for recovery

In coordinated checkpointing, all processes take their checkpoints together so that the set of checkpoints is a consistent global state.

Blocking two-phase protocol:

1. The coordinator takes a local checkpoint and sends CHECKPOINT_REQUEST to all processes.
2. A process receiving the request takes a tentative local checkpoint, stops sending application messages, and acknowledges.
3. After receiving all acknowledgements, the coordinator sends CHECKPOINT_DONE; each process makes its checkpoint permanent, discards the old one and resumes.

Non-blocking alternative: the Chandy-Lamport marker algorithm records the states using markers sent along the channels.

Coordinator   P1   P2   P3
   request --> ... tentative ckpt
   <-- ack ---
   done ----> permanent, resume

On a failure, all processes roll back to the last permanent checkpoint. This set is consistent, so there is no domino effect, and only one checkpoint per process needs to be stored; the cost is the coordination messages and the blocking delay.