--- title: "Dependability, K-fault, Byzantine" subject: "Distributed System" chapter: 9 key: "semester_7/distributed_system:dependability-kfault-byzantine" source: https://www.bctengineer.com/q/semester_7/distributed_system/dependability-kfault-byzantine site: BCT Engineering --- # Dependability, K-fault, Byzantine Distributed System · Chapter 9: Fault Tolerance - Asked in: 2070 Asar, 2+2+4 marks - Video: [Distributed Systems 2.4: Fault tolerance](https://www.youtube.com/watch?v=43TDfUNsM3E) — Martin Kleppmann - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/dependability-kfault-byzantine - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-9 ## Question What are the dependability requirements of fault tolerant system? What do you mean by K-fault tolerant? How to come to agreement in faulty system? Explain with the approach of byzantine generals problem. ## Short answer Dependability requirements include availability, reliability, safety, and maintainability. K-fault tolerance means the system survives up to K component failures; for Byzantine failures, 3K+1 replicas are needed for agreement. The Byzantine generals approach achieves agreement among n processes with m traitors by multi-round message exchange and majority voting, requiring n ≥ 3m+1. ## Answer #### Dependability requirements A fault tolerant system must be **dependable**, which covers: - **Availability**: the system is ready to be used immediately; it is the probability that the system works correctly at a given instant. - **Reliability**: the system runs continuously without failure over a time interval (high MTTF). - **Safety**: when the system fails, nothing catastrophic happens. - **Maintainability**: how easily a failed system can be repaired. (Often **security**, i.e. confidentiality and integrity, is also included.) #### K-fault tolerance 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. #### Agreement in a faulty system The **Byzantine generals problem** (Lamport, Shostak, Pease) models agreement in a system where some processes may be faulty and send wrong or conflicting messages (**Byzantine failure**: a process behaves arbitrarily, even maliciously). Several divisions of the Byzantine army surround a city, each commanded by a general. They must agree on a common plan (attack or retreat) by sending messages, but some generals are traitors who may tell different generals different things. Required: (1) all loyal generals decide on the same plan; (2) a small number of traitors cannot cause the loyal generals to adopt a bad plan. **Result**: with *m* faulty processes, agreement is possible only if the total number of processes is **n ≥ 3m + 1**, i.e. more than two-thirds are loyal. With 3 generals and 1 traitor, agreement is impossible. **Example with n = 4, m = 1** (general 3 is faulty): 1. Each general sends its value to all others: G1 sends 1, G2 sends 2, G3 sends 3 (but, being faulty, may send anything), G4 sends 4. 2. Each general collects the received values into a vector. For example, G1 has (1, 2, x, 4). 3. Each general sends its vector to all others. The faulty G3 sends arbitrary vectors. 4. Each general examines the i-th element of all the vectors it received and takes the **majority**; if there is no majority, the value is UNKNOWN. ```text G1 gets: (1,2,y,4) (a,b,c,d) (1,2,z,4) from G2,G3,G4 Majority per position -> (1, 2, UNKNOWN, 4) G2 and G4 reach the same result. ``` All loyal generals end with the same vector, and the entries for the loyal processes are correct. So the loyal generals agree, even though G3's value is unknown. **What we learn**: Byzantine faults are the hardest to tolerate; agreement needs 3m+1 processes and several rounds of messages (m+1 rounds), so it is costly. Byzantine agreement is used where failures can be arbitrary (aircraft control, other critical systems). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which describes reliability? A. Readiness at a given instant B. Running continuously without failure over a time interval C. Nothing catastrophic when it fails D. Ease of repair Answer: B. Availability is readiness at an instant; reliability is continuity over time. (Key point: Availability vs reliability) 2. Safety in dependability means: A. The system is easy to repair B. When it fails, nothing catastrophic happens C. It is always up D. Data is encrypted Answer: B. Safety concerns avoiding catastrophic consequences of failure. (Key point: Safety) 3. Why do 2K+1 replicas suffice for K arbitrary failures with voting? A. Faulty replicas are removed B. K+1 correct replicas outvote K faulty ones C. Each replica votes twice D. Majority is not required Answer: B. A majority of correct replicas wins the vote. (Key point: Byzantine voting) 4. With n=4 and one faulty general, what do all loyal generals end with? A. Different vectors B. The same vector, correct for loyal entries C. No vector D. Only the traitor's value Answer: B. Majority per position yields identical vectors with correct loyal values. (Key point: Faulty general result) ## Related in Distributed System - [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 - [Byzantine generals; recovery technique](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Abyzantine-recovery) — Distributed System, chapter 9 - [K-fault tolerant system; recovery](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Ak-fault-recovery) — Distributed System, chapter 9 - [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