Byzantine Agreement & The Phase King Algorithm
How distributed systems reach one decision even with faulty or adversarial nodes.
Overview
The Byzantine consensus problem addresses how multiple processes in a distributed system can agree on a single value, even when some processes behave arbitrarily or maliciously (Byzantine behavior). This is fundamental to building reliable distributed systems.
Any solution must satisfy three critical requirements: Validity (if all honest processes propose the same value X, they must decide X), Agreement (all honest processes must decide on the same value), and Termination (all processes must decide within finite time).
Byzantine Agreement Problem
Goal: All honest processes agree on one value
System Model
Key Assumptions:
- Synchronous system - Messages are delivered within known time bounds
- n processes total - Up to t of them can be Byzantine
- Classic bound:
n > 3t- Below this threshold, agreement cannot be guaranteed - "Byzantine" behavior - Arbitrary or malicious actions, including sending different messages to different processes
Algorithm: Phase King
The Phase King algorithm runs for t+1 rounds, where each round consists of two phases. This ensures at least one round has an honest king.
| Phase | Description | Action |
|---|---|---|
| Phase A Majority/Gradecast |
Everyone broadcasts their current value and counts support |
• Confidence 2 (strong): value seen by ≥ n−t processes • Confidence 1 (weak): some support • Confidence 0: no support If confidence 2 exists, keep that value |
| Phase B King Tie-break |
The designated king for this round broadcasts a value |
• If no strong majority (confidence < 2): adopt king's value • Otherwise: keep the strong-majority value |
Proof Sketch
The algorithm's correctness relies on two key invariants:
- Validity preservation: If all honest processes start with identical values, they maintain that value throughout the algorithm.
- Convergence guarantee: If the king is honest in any round, all honest processes will align on the same value by the end of that round.
Since the algorithm runs for t+1 rounds and at most t processes are Byzantine, at least one king must be honest. Therefore, the system achieves alignment within the time bound, satisfying Validity, Agreement, and Termination.
Worked Example
Setup: n = 4, t = 1 with initial values: (0, 0, 1, *) where * represents Byzantine behavior.
Round 1:
- Phase A: No value has strong majority (≥ 3 supporters), so confidence levels remain weak
- Phase B: King broadcasts a value (say 0). Since no strong majority exists, all honest processes adopt 0
Result:
After the first round, all honest processes converge on value 0. The Byzantine process cannot prevent this convergence, and the algorithm terminates successfully with agreement.
Limitations
The Phase King algorithm is specifically designed for synchronous networks where message delivery times are bounded and known. Fully asynchronous settings present additional challenges and require different approaches, often with probabilistic guarantees or additional assumptions like failure detectors.
The n > 3t bound is also fundamental - with fewer honest processes, Byzantine agreement becomes impossible in general, as shown by the famous "Byzantine Generals Problem."
Ready to explore hands-on?
See the Phase King algorithm in action with our interactive simulator
Open the App →