K-fault tolerant system; recovery

K-fault tolerant system

A system is K-fault tolerant if it can continue to provide correct service despite the failure of up to K components.

Basic principle (redundancy): replicate the components so that failures are masked.

• If processes fail silently (fail-stop/crash), K+1 replicas are enough: if K fail, at least one still works and gives the answer.
• If processes fail arbitrarily (Byzantine) and the group takes a majority vote, at least 2K+1 replicas are needed so that the K+1 correct ones outvote the K faulty ones. For agreement among Byzantine processes, 3K+1 are needed.

Example: a group of 5 servers with majority voting tolerates K = 2 arbitrary failures; with crash failures only, K+1 = 3 servers tolerate 2 crashes.

Fault recovery techniques

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.

Checkpointing and message logging are the practical methods of backward recovery:

• Independent checkpointing: each process saves its state at its own times; this may cause the domino effect.
• Coordinated checkpointing: processes save their states together so that they form a consistent global state; the latest set of checkpoints is the recovery line.
• Message logging: a process logs the messages it receives (pessimistic or optimistic logging) and, after restoring its last checkpoint, replays them to reach the state it had at the failure.

After recovery, the process takes up its work again, and orphan messages and processes are cleaned up.