Byzantine Generals Problem

distributedsystem

byz.pdf

The Story

Imagine several generals of the Byzantine army, each leading a division, have surrounded an enemy city. They must agree on a common plan: either attack or retreat. The key point is:

• If they all attack together, they’ll win.
• If some attack and others retreat, they’ll lose badly.

The Challenges

1. The generals are spread out, and can only communicate by sending messengers.
2. One or more generals might be traitors (Byzantine faults) who:
   • Send conflicting messages
   • Lie or behave unpredictably
   • Try to cause the loyal generals to disagree

The Problem

How can all loyal generals reach agreement, even if some of them are malicious?

Here’s where it gets tricky:

• Suppose General A sends “Attack at dawn” to both General B and C.
• A traitorous General A might send “Retreat at dusk” to C instead.
• Now B and C received conflicting information and don’t know whom to trust.

Even if the messengers are reliable, the **traitor can still manipulate the outcome**.

The Result:

This problem proves that:

• In a system with n generals, to tolerate f traitors, you need at least 3f + 1 total generals.
• That means: to tolerate 1 faulty node, you need at least 4 total nodes.

This insight is the basis for Byzantine Fault Tolerant (BFT) algorithms.

Real-World Relevance

• The problem models real-world distributed systems, especially in blockchains, distributed databases, and financial systems.
• Solutions like PBFT (Practical Byzantine Fault Tolerance) and Tendermint are used in systems where nodes may be compromised or behave maliciously.

Comparison: The Two Generals problem vs Byzantine Generals

Feature	Two Generals Problem	Byzantine Generals Problem
Goal	Two generals agree on whether to attack.	Multiple generals reach agreement on a plan (attack/retreat).
Type of Fault	Unreliable communication (messages may be lost).	Faulty/malicious nodes (traitors can lie or behave arbitrarily).
Trust Assumption	Both generals are honest.	Some generals may be malicious or traitorous.
Main Challenge	Can’t be sure a message was received (infinite acknowledgment loop).	Some nodes may lie and send conflicting messages to others.
Communication Channel	Faulty (messages may be lost).	Reliable, but nodes may be faulty (Byzantine behavior).
Problem Type	Agreement is impossible due to network unreliability.	Agreement is hard due to untrusted participants.
Solvability	Impossible with just 2 nodes over unreliable channels.	Solvable with ≥ 3f + 1 nodes to tolerate f faulty nodes.
Real-World Analogy	Email lost in spam folder—did they read it?	Group chat where one person lies to different members.
Typical Solution	No perfect solution. Approximated using retries, timeouts.	Solved using Byzantine Fault Tolerant algorithms (e.g., PBFT, Tendermint).

Summary

• Two Generals Problem = Problem with message delivery reliability
• Byzantine Generals Problem = Problem with trustworthiness of nodes.

Both problems inspired modern distributed consensus systems — but Byzantine fault tolerance is more general and harder to solve.

---

Distributed Systems 2.2: The Byzantine generals problem