Byzantine Generals Problem in Distributed Systems
"The Byzantine Generals Problem addresses how a group of generals, some of whom may be traitors, can reach a consensus on a battle plan while ensuring consistency, termination, and validity. Various protocols are explored to handle challenges such as faulty leaders, consistency violations, and cheating replicas in distributed systems."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Problem Formulation Byzantine Generals Problem Byzantine Generals Problem n n Byantine generals ( f f traitors) need to agree on a battle plan Attack Attack Requirements - Consistency - Termination - Validity Retreat Attack Attack Retreat Retreat Retreat 1
Protocol: First Try Round 1: leader proposes to all Round 2: all-to-all, commit upon f + 1 votes (assume messages are signed) Leader 1 Replica 1 Replica 2 Replica 3 n = 2f + 1 vote propose 2
Protocol: Faulty Leader (1) Leader may equivocate Check for equivocation before committing, i.e., commit = f + 1 votes and no equivocation Leader 1 Replica 1 v v Replica 2 v v Replica 3 n = 2f + 1 vote propose 3
Protocol: Faulty Leader (2) Cannot violate consistency But can hurt progress or cause replicas to progress differently Leader 1 Replica 1 Replica 2 v v v Replica 3 n = 2f + 1 vote propose 4
Protocol: Leader Change New leader needs to collect status reports when proposing status and attach status Leader 2 Leader 1 Replica 1 Replica 2 v Replica 3 n = 2f + 1 vote propose status 5
Protocol: Second Try Run (status, propose, commit) in iterations Leader 2 Leader 1 Replica 1 Replica 2 Replica 3 n = 2f + 1 propose vote propose status status 6
Protocol: Faulty Leader (3) Leader can still cheat Group 1 includes f faulty replicas Make replica 2 commit on v Leader 1 Group 1 v v v Replica 2 Group 3 n = 2f + 1 vote propose status 7
Protocol: Faulty Leader (3) Replica 2 committed on v, and vouches for it New leader: Replica 2 didn t send status Leader 1 Group 1 v Replica 2 v nil v Group 3 n = 2f + 1 vote propose status 8
Cause and Solution Want: 1 honest commit = f + 1 honest vouch An accept/notify round after commit Leader 1 Group 1 v v v v Replica 2 v Group 3 n = 2f + 1 notify vote propose status status 9
Core Protocol (status, propose, commit, notify) in iterations Leader 2 Leader 1 Group 1 Replica 2 Group 3 propose vote notify propose status status n = 2f + 1 10
When do Replicas Terminate? Terminate after receiving f+1 notify messages Leader 1 Group 1 v v v v Replica 2 v Group 3 n = 2f + 1 notify vote propose status status 11
Consistency Suppose h is the first honest replica to commit on a value v* in iteration k*, 1. A replica h cannot commit on v != v* in iteration k* - h must received f+1 commit messages on v - At least one of the f+1 messages is from an honest replica, say h - h would have sent v to h and h would detect equivocation, a contradiction 2. No other value v can be proposed in iterations k k* - 1 honest commit = f + 1 honest accept [Ensured by the Notify round] - Byzantine replicas cannot commit on v != v* in iteration k* 12
Termination Liveness/Termination: Honest leader termination Leader 3 Group 1 v Replica 2 v nil v Group 3 n = 2f + 1 vote propose status 13
Adapting to Byzantine Broadcast 1. How are leaders elected? 2. What value does the first leader propose? 14
Byzantine Broadcast - Designated sender s with value v - Validity? Agreement, termination are satisfied - Introduce a pre-round Sender s v v Leader 1 Group 1 v Replica 2 Group 3 vote notify propose status pre-round status n = 2f + 1 15
Byzantine Broadcast Pre-round, (status, propose, vote, notify), Assuming random leaders*, 2 iterations (8 rounds) in expectation, Sender s v v Leader 1 Group 1 v Replica 2 Group 3 vote notify propose status pre-round status n = 2f + 1 16
Metrics Round complexity Message complexity Byzantine Threshold Type of adversary 17
Metrics Round complexity: O(1) rounds, 10 rounds in expectation without considering election Message complexity: O(N2) signatures Byzantine Threshold: Minority Type of adversary: static 18
Dolev-Strong Protocol Round complexity: O(1) rounds, 10 rounds in expectation without considering election N rounds Message complexity: O(N2) signatures O(N2f) messages Byzantine Threshold: Minority to N-2 faults Type of adversary: static 19
Synchrony in Practice? The synchrony model has two requirements: - Bounded message delay - Locked-step execution Replica 1 Replica 2 20
BFT Clock Synchronization Run every day : - Send sync if a day has passed locally - Upon f+1 sync , start new day and broadcast Replica 1 Replica 2 Replica 3 n = 2f + 1 sync new-day 21
BFT Clock Synchronization - Run every day : - Send sync if a day has passed locally - Upon f+1 sync , start new day and broadcast - |clk(i) clk(j)| < d when a new day starts - |clk(i)-clk(j)| < d + t - Round time = d + (d + t) Lemma (Informal): For bounded message delay d, maximum clock drift b/w two honest replicas in a day is t, then set round time = 2d + t. 22
Key Idea Paxos Paxos Our Protocol Our Protocol Byzantine, synchronous f < n/2 PBFT PBFT Byzantine, asynchronous f < n/3 Not Byzantine, asynchronous f < n/2 quorum = f + 1 quorum = 2f + 1 Pre-commit quorum of f+1 Synchrony! Synchrony! Quorum intersection at 1 node Quorum intersection at f+1 nodes Post-commit quorum of 2f+1 23
