--- title: "Byzantine generals; K-fault principle" subject: "Distributed System" chapter: 9 key: "semester_7/distributed_system:byzantine-k-fault" source: https://www.bctengineer.com/q/semester_7/distributed_system/byzantine-k-fault site: BCT Engineering --- # Byzantine generals; K-fault principle Distributed System · Chapter 9: Fault Tolerance - Asked in: 2075 Chaitra, 3+5 marks - Video: [Byzantine Generals Problem and Byzantine Fault Tolerance Explained in Hindi l Blockchain Series](https://www.youtube.com/watch?v=3-qCkMzH4Fg) — 5 Minutes Engineering - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/byzantine-k-fault - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-9 ## Question What do you learn from Byzantine generals problem? Explain the basic principle of K-fault tolerant. ## Short answer The Byzantine generals problem shows that with m arbitrary faulty processes, agreement requires at least 3m+1 total processes, illustrating the high overhead of masking Byzantine faults. Basic principle of K-fault tolerance: replicate components; for crash failures, K+1 replicas; for Byzantine, 2K+1 for voting or 3K+1 for agreement. ## Answer #### Byzantine generals problem 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 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 (faulty may send anything), G4 sends 4. 2. Each general collects the received values as 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 vectors received and takes the **majority**; if 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 loyal processes are correct. So the loyal ones 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. It is used where failures can be arbitrary (aircraft control, critical systems). #### Basic principle of 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 suffice: 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. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. With m faulty processes, agreement in the Byzantine generals problem needs a total of at least: A. 2m processes B. 2m+1 processes C. 3m+1 processes D. m+1 processes Answer: C. n >= 3m+1, so more than two-thirds must be loyal. (Key point: Byzantine minimum) 2. Why is agreement impossible with 3 generals and 1 traitor? A. Messages are lost B. n=3 is less than 3m+1=4 C. Generals cannot send messages D. Majority voting always gives UNKNOWN Answer: B. The 3m+1 bound requires at least 4 generals for one traitor. (Key point: Three generals) 3. In the n=4, m=1 example, what is the final result for the faulty general's entry? A. The value 3 B. The value sent first C. UNKNOWN D. Zero Answer: C. No majority exists for the traitor's entry, so it is UNKNOWN, but loyal generals agree on it. (Key point: Vector majority) 4. How many replicas tolerate K crash (fail-silent) failures? A. K+1 B. 2K+1 C. 3K+1 D. K Answer: A. At least one of K+1 replicas still works. (Key point: Crash replicas) ## Related in Distributed System - [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 - [Byzantine generals; recovery technique](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Abyzantine-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 - [K-fault tolerant system; recovery](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Ak-fault-recovery) — Distributed System, chapter 9