Byzantine General's Problem

“Welcome to distributed systems: it’s basically a game of 3D Among Us where every other node is actively trying to scam you.”

The Origin Story

Before we talk about servers, let’s talk about the people who framed the problem. The Byzantine Generals Problem was formally introduced in a landmark 1982 paper by Leslie Lamport¹, Robert Shostak, and Marshall Pease.

At the time, they were working at SRI International² on a project called SIFT³ (Software Implemented Fault Tolerance), which was designed to fly aircraft using a network of computers. In an airplane, if a computer or sensor fails, it might just stop working (a simple “Fail-Stop”). But what if a glitch causes it to start sending wrong or deliberately conflicting data to the other flight computers?

To explain this incredibly complex issue of building reliable systems from unreliable, potentially “malicious” parts, Lamport devised the colorful allegory of the Byzantine army. (For the full military lore involving sieges, traitors, and messengers, see Byzantine Empire.)

The Distributed Systems Formalization

Let’s drop the swords and talk servers. In a distributed system, we want to build State Machine Replication (SMR). We have a set of $N$ nodes (replicas) that must process client requests in the exact same order, even if some nodes are completely compromised.

Let $f$ be the maximum number of faulty (Byzantine) nodes. These nodes can crash, drop messages, send conflicting messages, or actively collude to break the system.

To achieve Byzantine Fault Tolerance (BFT), the consensus protocol must guarantee two properties:

1. Safety (Agreement): All honest nodes execute the same sequence of requests. (They don’t diverge, no matter what the network does).
2. Liveness (Termination): Honest clients eventually receive replies to their requests. (The system doesn’t stall indefinitely).

The Impossibility Result: The $3f$ Trap

Can we achieve consensus if we have 3 nodes and 1 is malicious ($N=3, f=1$)? No. Imagine the setup: Primary Node ($P$), Replica 1 ($R_1$), Replica 2 ($R_2$).

• Scenario A (Malicious Primary): $P$ tells $R_1$ to “Write X=1” and $R_2$ to “Write X=2”. $R_1$ and $R_2$ cross-check. $R_1$ says ”$P$ said 1!” $R_2$ says ”$P$ said 2!”. Who is lying? $P$, or the other replica? It is mathematically impossible for an honest replica to know.
• Scenario B (Malicious Replica): $P$ is honest and says “Write X=1”. Malicious $R_2$ tells $R_1$, “Actually, $P$ told me X=2.” $R_1$ is in the exact same state of confusion as Scenario A.

(Insert “Spider-Man pointing at Spider-Man” meme here, but it’s three servers throwing HTTP 400 errors at each other)

The Mathematical Theorem

Theorem: In a system with oral (unauthenticated but unforgeable) messages, tolerating $f$ Byzantine faults requires strictly more than $3f$ total nodes.

Therefore, the golden rule of BFT is:

Practical Byzantine Fault Tolerance

For a long time, BFT was considered too slow and message-heavy for real-world use. Then, in 1999, Miguel Castro and Barbara Liskov introduced PBFT - Practical Byzantine Fault Tolerance.

PBFT proved you could actually process thousands of requests per second in a Byzantine environment. It relies heavily on cryptography (signatures/MACs) and a primary-backup model.

How PBFT Works (The 3-Phase Commit)

PBFT operates in “views” (epochs). In each view, one node is the Primary, and the rest are Backups. When a client sends a request, the network goes through three phases to agree on its order:

1. Pre-Prepare: The Primary assigns a sequence number to the client’s request and broadcasts a <<PRE-PREPARE>> message to all backups.
2. Prepare: Backups receive the pre-prepare. If it looks valid, they broadcast a <<PREPARE>> message to everyone.

• Checkpoint: Once a node receives $2f$ matching <<PREPARE>> messages (plus its own), it has a prepared certificate. At this point, the network agrees on the sequence number.

3. Commit: Nodes broadcast a <<COMMIT>> message. Once a node receives $2f+1$ matching <<COMMIT>> messages, it executes the request and replies to the client.

Yo dawg, I heard you like consensus, so I put an agreement phase inside your agreement phase so you can agree that you agreed.

Why all the phases?

• Pre-prepare & Prepare ensure ordering within a single view (even if the Primary is evil).
• Commit ensures the decision survives a View Change (if the Primary crashes or is proven to be malicious, the network elects a new Primary and needs to know which requests were actually finalized).

PBFT guarantees Safety in purely asynchronous networks (no bounds on message delays), but it requires a weakly synchronous network to guarantee Liveness (otherwise a malicious primary could just delay messages forever without triggering a timeout).

Conclusion (?)

While PBFT is brilliant for permissioned, closed networks (like Hyperledger Fabric or a consortium of banks), it requires $O(N^2)$ message complexity. Every node talks to every other node. If you have 10,000 nodes, the network chokes on the math. This quadratic complexity makes it impractical for large-scale, open, and permissionless networks like public blockchains, necessitating alternative consensus mechanisms. $\rightarrow$ Proof of Work