Beyond crash faults
Classic Paxos assumes faulty nodes simply stop. Byzantine faults are worse: a node may send conflicting messages, forge values, or behave arbitrarily, perhaps because it is compromised. Byzantine Paxos strengthens the protocol to agree correctly despite such adversarial participants.
More replicas, more confirmation
To tolerate f Byzantine faults, the system needs at least 3f plus 1 replicas, not 2f plus 1. The reason is that a single majority can include liars, so honest nodes must cross check each other.
- Acceptors do not trust a proposer blindly; they exchange messages to confirm what others heard.
- A value is chosen only when enough independent acceptors, more than a simple majority, certify the same proposal.
- Cryptographic signatures or message authentication codes prevent a faulty node from forging another node's vote.
Why the bound grows
With 3f plus 1 nodes, any two quorums of size 2f plus 1 overlap in at least f plus 1 nodes, guaranteeing at least one honest node in the intersection. That honest witness ties decisions together so liars cannot create two different chosen values.
Key idea
Byzantine Paxos tolerates arbitrary faults by using 3f plus 1 replicas, mutual cross checking, and authentication so liars cannot force two different decisions.