The Byzantine Generals Problem

I came across this on LinkedIn — a post about a GitHub outage that lasted roughly 70 minutes. What made it interesting wasn't the outage itself. It was why it happened.

Here's what made it a cascade instead of just a blip: every well-behaved HTTP client is supposed to re-authenticate when it gets a 401. So thousands of apps did exactly the right thing — and made everything worse.

Every client getting a false 401 kicked off a token refresh, which piled more load onto an already-struggling auth layer. More load → more false 401s → more token refreshes → repeat. A feedback loop that turned a partial failure into a platform-wide incident.

The key takeaway from the post:

Then I saw this reply in the comments:

The commenter was pointing at something real — the GitHub incident is a textbook example of a Byzantine failure. The auth system wasn't crashed. It wasn't offline. It was actively respondingwith incorrect information. And that's far more dangerous than a clean crash, because nothing knows to stop trusting it.

That comment sent me down a rabbit hole. Let me explain what Byzantine Failures actually are — and why there's a 40-year-old theorem that predicts exactly how bad this can get.

In 1982, Leslie Lamport, Robert Shostak, and Marshall Pease published a paper describing a problem they called the Byzantine Generals Problem.

Imagine a group of generals of the Byzantine army surrounding an enemy city. Each general commands a separate division of troops. They must agree on a unified plan — either all attack or all retreat. A divided action (some attack, some retreat) is worse than either choice alone.

The only way they can communicate is via messengers. The problem: some generals may be traitors, sending conflicting orders to different generals to sabotage consensus.

The auth layer wasn't sending no response (crash failure). It wasn't timing out (timing failure). It was confidently, actively lying— telling clients their valid tokens were invalid. That's Byzantine failure. And it's the hardest kind to handle precisely because nothing looks broken from the outside.

Not all failures are created equal. Distributed systems face four categories:

Byzantine is the hardest because the node is still running— it just can't be trusted. In the GitHub case, the auth nodes were happily returning 401s. Health checks probably showed them as "healthy." Dashboards were green. And yet they were lying to every client that touched them.

Lamport et al. proved a fundamental mathematical limit: to tolerate f Byzantine (lying) nodes, you need at least 3f + 1 total nodes.

f = number of Byzantine nodes you want to tolerate
n = minimum total nodes required

n ≥ 3f + 1

Examples:
  f = 1 lying node  →  n = 4 nodes minimum
  f = 2 lying nodes →  n = 7 nodes minimum
  f = 10 lying nodes → n = 31 nodes minimum

Why 3f + 1? Consider f nodes sending false data. To outvote them, honest nodes need a 2-to-1 majority — so you need at least 2f + 1 honest nodes. Add the f liars back: 2f + 1 + f = 3f + 1.

With only 3f nodes, a lying node can make two groups of honest nodes each think the other group is compromised. Consensus breaks. The +1 is not optional — it's the mathematical minimum for truth to win.

This is also why the circuit-breaker pattern matters so much. If your system doesn't have enough independent nodes to vote, you need a different mechanism — stop trusting, alert, back off. Don't amplify the liar.

Paxos and Raft use only 2f + 1 nodes to tolerate f failures. The difference comes down to what a faulty node actually does.

A crashed node is silent — it casts no vote. So with 2f + 1 nodes, the f + 1 honest responders always outvote the f absent ones. Simple.

A Byzantine node responds — but sends different messages to different people. With 3 nodes (Alice, Bob, Byzantine Commander):

Commander → Alice: "ATTACK"
Commander → Bob:   "RETREAT"   ← different message, same sender

After sharing:
  Alice sees: { ATTACK from Commander, RETREAT from Bob }  →  1 vs 1  tie ✗
  Bob sees:   { RETREAT from Commander, ATTACK from Alice }  →  1 vs 1  tie ✗

With 4 nodes (Alice, Bob, Carol honest — Dave traitor), Dave lies to everyone but is outvoted 2-to-1 because Alice and Bob cross-confirm each other:

Alice sees: { Bob→ATTACK, Dave→RETREAT, Commander→ATTACK }  →  2 vs 1  ATTACK ✓
Bob sees:   { Alice→ATTACK, Dave→RETREAT, Commander→ATTACK }  →  2 vs 1  ATTACK ✓

With 3 nodes a lie creates a 1-1 tie. With 4 nodes it creates a 2-1 majority. That fourth node — the extra f — is what makes truth provably winnable.

Lamport's Oral Messages algorithm solves consensus recursively. The intuition: the commander sends an order, then each lieutenant re-broadcasts what they received to everyone else. After enough rounds, honest nodes take the majority vote — and the liars get drowned out.

The rules for honest nodes:

1. Send your decision to every other node.
2. Forward every message you receive to all others (so everyone has the same information).
3. Use majority voting — whatever most nodes say, do that.
4. If messages contradict each other, default to the safe option.

Here's a C++ implementation:

The lying node tried to send conflicting messages — but 3 honest nodes out of 4 always outvote it. The system converges on truth.

Back to the GitHub incident. The comment mentioned exponential back-off as the answer. That's correct, but let's be precise about why.

When you get a 401 on a freshly-minted token, you're in a Byzantine failure scenario — the auth system is lying. Retrying doesn't help. You need a circuit breaker:

With a circuit breaker, thousands of apps wouldn't have piled onto GitHub's auth layer. They'd have tripped their breakers after the first handful of false 401s, stopped sending requests, and waited. The auth layer would have had room to recover.

The GitHub outage was a real-world Byzantine failure. The fix wasn't just "fix the auth bug" — it was also every client needing a circuit breaker so one lying layer couldn't amplify itself into a platform-wide outage.

Next time you're implementing retry logic, remember: consecutive failures on a freshly-refreshed token aren't a reason to retry. They're a reason to stop, back off, and let the system breathe.

• ↗GitHub Outage — The LinkedIn Post That Started ThisArpit Bhayani on LinkedIn
• ↗The Byzantine Generals Problem — Deep DiveMatthew Thorne on LinkedIn