Q22Distributed Systems

In standard fault tolerance (Fail-Stop), a server simply crashes and stops responding. This is easy to mathematically detect. The Byzantine Generals Problem (formulated by Lamport) models the absolute worst-case scenario: Byzantine Failure. The server does not crash. Instead, it is physically compromised (hacked or suffering horrific hardware corruption) and mathematically lies, sending completely conflicting data to different nodes in the cluster to intentionally trigger a catastrophic systemic collapse.

Imagine a Byzantine army surrounding a city. The army is split into divisions, commanded by Generals (Server Nodes) who can only communicate via messengers (Network). They must reach an absolute mathematical consensus: either ALL attack, or ALL retreat. If half attack, they are annihilated.

• The absolute complication: Some Generals are traitors (Hacked Nodes).
• A Traitorous General will mathematically send a message "ATTACK" to General A, but simultaneously send "RETREAT" to General B.
• General A and General B are loyal, but they now possess completely conflicting data and do not mathematically know who is lying.

Lamport mathematically proved that if the system contains $m$ traitorous (faulty) nodes, the system MUST contain a minimum of $N=3m+1$ total nodes to violently force consensus. The number of loyal nodes must fiercely overpower the traitors.

• Example ($m=1$ Traitor): You mathematically need $N=3(1)+1=4$ total nodes. You need 3 loyal nodes to outvote 1 traitor.
• Why 3 nodes ($N=3$) mathematically fails: Assume Commander (Traitor) tells Lieutenant 1 to Attack, and Lieutenant 2 to Retreat. L1 tells L2 "Commander said Attack". L2 is now holding "Attack" from L1 and "Retreat" from Commander. L2 mathematically cannot determine if the Commander is the traitor, or if L1 is the traitor. Consensus violently fails.

Modern distributed blockchains and aerospace flight computers must survive Byzantine failures.

• Practical Byzantine Fault Tolerance (PBFT): An aggressive algorithm that uses three strict phases (Pre-Prepare, Prepare, Commit) with massive cryptographic signing. A node mathematically requires a two-thirds majority quorum of identically cryptographically signed messages before it violently executes an action to the ledger, completely paralyzing any malicious node attempting to inject corrupt data.