---
title: "K-fault tolerant system; recovery"
subject: "Distributed System"
chapter: 9
key: "semester_7/distributed_system:k-fault-recovery"
source: https://www.bctengineer.com/q/semester_7/distributed_system/k-fault-recovery
site: BCT Engineering
---

# K-fault tolerant system; recovery

Distributed System · Chapter 9: Fault Tolerance

- Asked in: 2074 Asoj, 2+6 marks
- Video: [Fault Tolerance | System Design](https://www.youtube.com/watch?v=DNam6NbjgW4) — Techdose Engineering
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/distributed_system/k-fault-recovery
- Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-9

## Question

What is K-fault tolerant system? Explain fault recovery techniques.

## Short answer

A K-fault tolerant system survives failure of up to K components through redundancy. For crash failures, K+1 replicas suffice; for Byzantine, 2K+1 for voting, 3K+1 for agreement. Recovery techniques: backward recovery (checkpoint/rollback) loses recent work; forward recovery corrects errors without rollback, needing advance error knowledge.

## Answer

#### 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.

| Point | Backward recovery | Forward recovery |
|---|---|---|
| Idea | Roll back to saved state | Move to new correct state |
| Error knowledge | Not needed | Needed in advance |
| Overhead | Checkpoint cost, lost work | Less, but designed per error |
| Generality | General | Specific |
| Example | Checkpoint/restart | Error-correcting codes |

**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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. A K-fault tolerant system:
   A. Has exactly K components
   B. Continues to give correct service despite failure of up to K components
   C. Fails after K faults
   D. Needs K checkpoints
   Answer: B. K counts the number of component failures it can survive. (Key point: K-fault tolerant)

2. How many replicas are needed to tolerate K arbitrary failures with majority voting?
   A. K+1
   B. 2K
   C. 2K+1
   D. 3K+2
   Answer: C. The K+1 correct replicas must outvote K faulty ones. (Key point: Byzantine replicas with voting)

3. A group of 5 servers with majority voting under arbitrary failures tolerates:
   A. K=1
   B. K=2
   C. K=3
   D. K=4
   Answer: B. 2K+1=5 gives K=2. (Key point: Example)

4. What is the recovery line in coordinated checkpointing?
   A. The first checkpoint ever taken
   B. The latest consistent set of checkpoints to which all processes roll back
   C. The message log
   D. The newest message received
   Answer: B. Processes save states together forming a consistent global state; the latest is the recovery line. (Key point: Coordinated checkpointing)

## Related in Distributed System

- [Reasons for replication; fault tolerant services](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Areplication-reasons-ft-services) — Distributed System, chapter 7
- [Transaction recovery techniques](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Atransaction-recovery) — Distributed System, chapter 8
- [Fault tolerance techniques](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Afault-tolerance-techniques) — Distributed System, chapter 9
- [Byzantine generals; K-fault principle](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Abyzantine-k-fault) — Distributed System, chapter 9
- [Fault tolerance; Byzantine failure](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Abyzantine-failure-agreement) — Distributed System, chapter 9
- [Dependability, K-fault, Byzantine](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adependability-kfault-byzantine) — Distributed System, chapter 9

## Related in other subjects

- [Software fault tolerance and recovery](https://www.bctengineer.com/question.md?key=semester_5%2Finstrumentation_ii%3Asw-fault-tolerance-rollback) — Instrumentation II, chapter 9, asked 2×
- [Cable fault location techniques and Murray loop](https://www.bctengineer.com/question.md?key=semester_4%2Fpower_system_analysis_i%3Acable-fault-techniques-murray) — Power System Analysis I, chapter 2
- [Digital carrier system and multiplexing techniques](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Adigital-carrier-multiplexing) — Telecommunications, chapter 3
- [Solid waste management system and techniques](https://www.bctengineer.com/question.md?key=semester_7%2Fenvironment_and_pollution_control%3Asolid-waste-management-techniques) — Environment and Pollution Control, chapter 5