--- title: "Fault tolerance; Byzantine failure" subject: "Distributed System" chapter: 9 key: "semester_7/distributed_system:byzantine-failure-agreement" source: https://www.bctengineer.com/q/semester_7/distributed_system/byzantine-failure-agreement site: BCT Engineering --- # Fault tolerance; Byzantine failure Distributed System · Chapter 9: Fault Tolerance - Asked in: 2070 Chaitra, 1+2+5 marks - Video: [Distributed Systems 2.2: The Byzantine generals problem](https://www.youtube.com/watch?v=LoGx_ldRBU0) — 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/byzantine-failure-agreement - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-9 ## Question What do you mean by fault tolerant system? What do you mean by Byzantine Failure? Explain Byzantine Generals problem to illustrate how agreement can be reached in faulty system. ## Short answer A fault tolerant system continues correct service despite component failures using redundancy. Byzantine failure is an arbitrary failure where a process may produce wrong or malicious responses. The Byzantine generals problem illustrates agreement: with n≥3m+1 processes (m traitors), loyal generals exchange and compare vectors in multiple rounds, taking majority to reach a common decision. ## Answer #### Fault tolerant system A **fault tolerant system** continues to provide correct service even when faults occur in its components. It does so by redundancy (information, time and physical) and by detecting, masking and recovering from faults. #### Byzantine failure A **Byzantine failure** (arbitrary failure) is a failure in which a process behaves in an arbitrary way: it may produce wrong results, send different values to different processes, or even act maliciously, and it may do so without being detected. It is the hardest class of failure. #### Agreement through the 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). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. A fault tolerant system: A. Never has faults B. Continues correct service even when component faults occur C. Stops when a fault is detected D. Has no redundancy Answer: B. It uses redundancy and detection, masking and recovery. (Key point: Fault tolerant system) 2. A Byzantine failure is: A. A process halting cleanly B. A process behaving arbitrarily, possibly sending different values to different processes C. A late response only D. A lost message Answer: B. It is an arbitrary, possibly malicious failure and the hardest class. (Key point: Byzantine failure) 3. What does agreement with m Byzantine faults cost? A. 3m+1 processes and about m+1 rounds of messages B. m processes and one round C. 2m processes and two rounds D. One process and no messages Answer: A. Byzantine agreement is expensive in both processes and rounds. (Key point: Rounds cost) ## 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 - [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 - [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 - [Replication, fault tolerance, scalability](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Areplication-scalability-ft) — Distributed System, chapter 7 ## 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× - [Availability and fault tolerance in GFS](https://www.bctengineer.com/question.md?key=semester_8%2Fbig_data_technologies%3Agfs-availability-fault-tolerance) — Big Data Technologies, chapter 2 - [Fault tolerance and redundancy for reliability](https://www.bctengineer.com/question.md?key=semester_5%2Finstrumentation_ii%3Afault-tolerance-schemes) — Instrumentation II, chapter 7, asked 4× - [MapReduce worker failure tolerance](https://www.bctengineer.com/question.md?key=semester_8%2Fbig_data_technologies%3Amapreduce-fault-tolerance) — Big Data Technologies, chapter 3