The Byzantine Generals Problem

Imagine several divisions of the Byzantine army camped around an enemy city, each commanded by a general. They can win only if they all attack or all retreat together — a half-hearted, split assault is the worst outcome. The generals can communicate only by messenger, and here is the catch: some generals may be traitors who deliberately send different messages to different colleagues to wreck any agreement.

The question, posed by Leslie Lamport, Robert Shostak and Marshall Pease in 1982, is deceptively simple: can the loyal generals agree on a single plan, even though they don't know who the traitors are and the traitors are actively lying?

It sounds like a war story, but it is really the core problem of every system where independent computers must agree while some of them are faulty or malicious — and the answer comes with a precise, unforgiving threshold.

A loyal commander sends an order. Each lieutenant relays what it heard to the others, then everyone takes a majority vote. The traitor sends conflicting values to poison the count. Change the number of generals and traitors and watch what happens to agreement.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>{{lbl_total}}
    <select id="total">
      <option value="4">4</option>
      <option value="6">6</option>
      <option value="7">7</option>
    </select>
  </label>
  <label>{{lbl_traitors}}
    <select id="traitors">
      <option value="1">1</option>
      <option value="2">2</option>
    </select>
  </label>
  <label>{{lbl_order}}
    <select id="order">
      <option value="ATTACK">ATTACK</option>
      <option value="RETREAT">RETREAT</option>
    </select>
  </label>
</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
</div>
<div id="generals" class="generals"></div>
<div class="status" id="status">{{status_init}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: 1rem; flex-wrap: wrap; margin: .4rem 0 .8rem; }
label { font-size: .82rem; font-weight: 600; color: #1d3557; display: flex; flex-direction: column; gap: .25rem; }
select { font: 600 14px system-ui, sans-serif; padding: .35rem .5rem; border: 1px solid #adb1b8; border-radius: 6px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
.generals { display: grid; grid-template-columns: repeat(auto-fit, minmax(120px, 1fr)); gap: .55rem; margin: .5rem 0; }
.gen { border: 1px solid #cdd9e3; border-radius: 10px; padding: .55rem .6rem; background: #f4f7fa; }
.gen .name { font-weight: 700; font-size: .9rem; color: #1d3557; display: flex; align-items: center; gap: .35rem; }
.gen.traitor { background: #fdecee; border-color: #f3b6bd; }
.gen.traitor .name { color: #c92f3c; }
.gen .role { font-size: .72rem; color: #667; margin: .1rem 0 .35rem; }
.gen .decision { font-weight: 700; font-size: .95rem; }
.gen .decision.attack { color: #0a7d33; }
.gen .decision.retreat { color: #b9770a; }
.badge { font-size: .62rem; font-weight: 700; padding: .05rem .35rem; border-radius: 99px; background: #1d3557; color: #fff; }
.badge.t { background: #c92f3c; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }

// Code not found

Notice the threshold. With 4 generals and 1 traitor the three loyal ones still lock onto the same order — because more than two-thirds are honest. Push to 6 generals and 2 traitors and the guarantee evaporates: honest votes can no longer outweigh the lies. The line between "safe" and "broken" is exactly n > 3 × (traitors).

How hard is Byzantine agreement, really? The surprising part is not the algorithm — it's the boundary.

• Checking a proposed protocol is one thing; proving when agreement is even possible is the deep result.
• The two-thirds law. Lamport, Shostak and Pease proved that with f traitors, the loyal generals can be guaranteed to agree if and only if the total number of generals is more than 3f — that is, more than two-thirds must be honest. With 1 traitor you need at least 4 generals; with 2 traitors, at least 7.
• It is a sharp impossibility, not a heuristic. Below the threshold no algorithm works, no matter how clever. A traitor sending one general "attack" and another "retreat" can always be balanced so the honest ones cannot tell truth from lie.
• Rounds cost messages. Tolerating f traitors requires f + 1 rounds of messaging in the classic oral-messages algorithm, and the message count grows quickly — a real complexity price for robustness.

That is the punchline: Byzantine fault tolerance is a solved problem with an exact frontier. Like the hardness results behind P vs NP, the value isn't a recipe — it's knowing precisely where the wall is and that you cannot build past it.

"Agree on one value even though some participants are lying" is the heartbeat of modern distributed systems, and the generals are its friendly face:

• Blockchains and cryptocurrencies: proof-of-stake and classic BFT chains assume fewer than one-third of validators are malicious — the generals' threshold, restated for money.
• Aerospace and avionics: flight-control computers vote on sensor readings so a single faulty unit can't crash the plane; the redundancy is sized by the two-thirds rule.
• Replicated databases: systems that keep copies in sync across data centers use Byzantine-fault-tolerant consensus to survive corrupted or compromised replicas.
• Teaching distributed systems: because the siege metaphor is so vivid, the generals are the canonical on-ramp to what "consensus under adversaries" even means.

Understand why the generals need a two-thirds majority and you've met the same constraint that bounds consensus-style agreement across every fault-tolerant network we build.

The Byzantine Generals problem hides a beautiful, exact truth: a group of honest participants can reach agreement while liars do their worst — but only if more than two-thirds of them are loyal. Cross that line and no protocol, however ingenious, can save you.

So the next time a blockchain boasts that it tolerates malicious validators, or an aircraft votes across triple-redundant computers, remember the generals at the city walls. The same threshold that lets loyal commanders coordinate an attack is the one quietly deciding whether you can trust a machine you cannot see — a frontier as firm as anything in P vs NP.