--- title: "Byzantine generals; recovery technique" subject: "Distributed System" chapter: 9 key: "semester_7/distributed_system:byzantine-recovery" source: https://www.bctengineer.com/q/semester_7/distributed_system/byzantine-recovery site: BCT Engineering --- # Byzantine generals; recovery technique Distributed System · Chapter 9: Fault Tolerance - Asked in: 2071 Chaitra, 8 marks - Video: [What is Byzantine Fault Tolerance｜Explained For Beginners](https://www.youtube.com/watch?v=VWG9xcwjxUg) — Binance Academy - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/byzantine-recovery - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-9 ## Question Explain Byzantine general problem to handle faulty process with example. Describe any one failure recovery technique. ## Short answer In the Byzantine generals problem, n processes must agree despite m traitors, possible only if n ≥ 3m+1. With 4 generals and 1 traitor, loyal ones exchange vectors and take majority, reaching agreement. Coordinated checkpointing is a backward recovery technique: a coordinator asks all processes to take consistent checkpoints; on failure, they roll back to the recovery line. ## 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). #### Failure recovery technique: checkpointing (backward recovery) After a failure, the system restores a previously saved consistent state and continues. 1. Each process saves its state (a **checkpoint**) on stable storage. 2. In **coordinated checkpointing**, a coordinator asks all processes to take tentative checkpoints, then makes them permanent, giving a consistent global state (no orphan messages). 3. When a process fails, all processes roll back to the latest checkpoint (the **recovery line**), and execution restarts. Logged messages can be replayed to recover the work done after the checkpoint. Its limit is the lost work since the last checkpoint and the cost of saving; it does not handle Byzantine (arbitrary) faults, which need voting and agreement. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which are the two requirements of the Byzantine generals problem? A. All generals attack; traitors are removed B. All loyal generals decide on the same plan; a few traitors cannot cause a bad plan C. Every message is acknowledged; no message is lost D. Majority attacks; minority retreats Answer: B. Agreement among loyal generals and resistance to a few traitors. (Key point: Loyal generals' goals) 2. In the 4-general example, what do generals send in the second round? A. Their own value again B. Their collected vector of received values C. Only a yes/no vote D. Nothing Answer: B. Each sends its vector, then takes the majority at each position. (Key point: Two message steps) 3. In coordinated checkpointing, what gives a consistent global state? A. Each process checkpoints at random B. A coordinator makes all processes take tentative checkpoints then makes them permanent C. Only the coordinator saves state D. Messages are discarded Answer: B. Coordinated tentative then permanent checkpoints avoid orphan messages. (Key point: Coordinated checkpoint) 4. Why does checkpointing not solve Byzantine faults? A. Checkpoints are too slow B. It restores earlier state but does not handle arbitrary faulty behaviour, which needs voting and agreement C. It needs 3m+1 processes D. Checkpoints cannot be stored Answer: B. Rollback does not detect or mask processes behaving arbitrarily. (Key point: Checkpoint limitation) ## 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 - [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 - [One election technique; consensus steps](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aelection-technique-consensus) — Distributed System, chapter 6 - [Distributed deadlock and recovery](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adistributed-deadlock-note) — Distributed System, chapter 8, asked 3× ## Related in other subjects - [General, local and punching shear failure](https://www.bctengineer.com/question.md?key=semester_5%2Ffoundation_engineering%3Amodes-shear-failure) — Foundation Engineering, chapter 6, asked 4× - [General vs one-class CF](https://www.bctengineer.com/question.md?key=semester_8%2Finformation_system%3Ageneral-vs-one-class-cf) — Information System, chapter 7 - [General process of creating a PCB](https://www.bctengineer.com/question.md?key=semester_5%2Finstrumentation_ii%3Apcb-creation-process) — Instrumentation II, chapter 8 - [Near-far effect and a hybrid SS technique](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Anear-far-hybrid-technique) — Wireless Communication, chapter 7