Weak Byzantine Generals
Summary
The Weak Byzantine Generals (WBG) problem is a relaxation of the Byzantine Generals problem introduced by Lamport [1]. In the standard Byzantine Generals problem, if the broadcaster is honest, then all non-faulty processes must output the broadcaster's value (validity), and all non-faulty processes must agree (agreement). The weak variant relaxes validity: it only requires that if all processes are non-faulty, then they all output the broadcaster's value.
Formal Definition
Consider \(n\) processes, at most \(t\) of which may be Byzantine faulty. A Weak Byzantine Generals protocol satisfies the following two conditions [2]:
- Agreement: Any two non-faulty processes take the same final action.
- Weak Validity: If no process is faulty and all processes initially choose the same action, then that is the final action taken by all processes.
Compare this with the standard Byzantine Generals (broadcast) definition, which requires:
- Agreement: All non-faulty processes agree on the same value.
- Validity: If the broadcaster is non-faulty, then all non-faulty processes output the broadcaster's value.
The key difference is in the validity condition: BG requires agreement with the broadcaster's value whenever the broadcaster is honest, whereas WBG only requires this when every process is honest.
Bounds
- Resilience: WBG can be solved for any \(t < n\) [1]. This is in contrast to standard BG, which requires \(t < n/3\) without signatures.
- Round complexity: Tolerating \(t\) faults requires at least \(t+1\) rounds [3].
- Unauthenticated setting: Without digital signatures, the protocol for \(t < n\) may require an infinite number of messages (i.e., it does not guarantee termination) [1].
- Authenticated setting: With digital signatures, WBG is subsumed by standard BG, which can be solved for any \(t < n\) with termination using protocols like Dolev Strong Broadcast Protocol (\(t+1\) rounds).
- Approximate agreement relaxation: If processes are allowed to output values within some \(\varepsilon\) of each other (approximate agreement), then there exists a finite algorithm for any \(t < n\) even without signatures [1, 4].
Relationship to Transaction Commit
The Commit Protocols problem in distributed databases is an instance of WBG [2]. In transaction commit, \(n\) processes each start with a vote of either commit (1) or abort (0), and must agree on a final decision satisfying:
- Agreement: No two processes decide differently.
- Validity: If any process starts with 0, then 0 is the only possible decision. If all processes start with 1 and there are no failures, then 1 is the only possible decision.
The validity condition here mirrors weak validity: the "good" outcome (commit) is only guaranteed when every process votes for it and none fail. This equivalence implies that the \(t+1\) round lower bound for tolerating \(t\) faults in WBG applies to commit protocols as well.
Notes
- First introduced by Lamport [1].
- The original protocol assumes a synchronous network with no digital signatures (unauthenticated).
- Synchrony is inherent: even though validity is weakened, agreement must still hold when faults occur. FLP impossibility [5] therefore rules out deterministic asynchronous solutions.