Introduction

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.

Run a Round

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">A loyal commander sends an order. One general is a <b>traitor</b> who relays conflicting messages. Loyal generals forward what they heard and then take a <b>majority vote</b>. Agreement is guaranteed only while more than two-thirds of the generals are loyal.</p>
<div class="controls">
  <label>Total generals
    <select id="total">
      <option value="4">4</option>
      <option value="6">6</option>
      <option value="7">7</option>
    </select>
  </label>
  <label>Traitors
    <select id="traitors">
      <option value="1">1</option>
      <option value="2">2</option>
    </select>
  </label>
  <label>Commander's 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">Run a round</button>
</div>
<div id="generals" class="generals"></div>
<div class="status" id="status">Choose a setup and run a round.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// The Byzantine Generals problem (Lamport, Shostak & Pease, 1982).
// A loyal commander broadcasts one order. Each lieutenant relays what it heard to
// the others; a TRAITOR sends conflicting values to sow discord. Every loyal
// lieutenant then takes the MAJORITY of the values it collected. The one-round
// Oral-Messages algorithm OM(1) reaches agreement iff n > 3*f, i.e. more than
// two-thirds of the generals are loyal.
const $ = id => document.getElementById(id);

function majority(values, fallback){
  const tally = {};
  values.forEach(v => tally[v] = (tally[v]||0)+1);
  let best = null, bestN = -1, tie = false;
  for(const v in tally){ if(tally[v] > bestN){ best = v; bestN = tally[v]; tie = false; }
                         else if(tally[v] === bestN){ tie = true; } }
  return tie ? fallback : best;
}

function run(){
  const n = +$('total').value;
  const f = +$('traitors').value;
  const order = $('order').value;
  const OTHER = order === 'ATTACK' ? 'RETREAT' : 'ATTACK';

  // General 0 is the loyal commander. The last f lieutenants are traitors.
  // Lieutenants are generals 1..n-1.
  const lieutenants = [];
  for(let i=1;i<n;i++) lieutenants.push(i);
  const traitorSet = new Set(lieutenants.slice(lieutenants.length - f));

  // Round 1: commander sends the true order to every lieutenant.
  // Round 2: each lieutenant relays the value it received to the others.
  // A loyal lieutenant relays the true order; a traitor lies maximally,
  // always relaying the OPPOSITE order to poison every majority vote.
  function relayed(from, to){
    if(!traitorSet.has(from)) return order;              // loyal: honest relay
    return OTHER;                                        // traitor: always lies
  }

  // Each loyal lieutenant collects: its own received value + relays from peers.
  const decisions = {};
  lieutenants.forEach(L => {
    if(traitorSet.has(L)) return;                        // traitors have no honest decision
    const collected = [order];                           // value received from commander
    lieutenants.forEach(P => { if(P!==L) collected.push(relayed(P, L)); });
    decisions[L] = majority(collected, order);
  });

  // Render
  const wrap = $('generals'); wrap.innerHTML = '';
  const card = (idx, role, isTraitor, decision) => {
    const d = document.createElement('div');
    d.className = 'gen' + (isTraitor ? ' traitor' : '');
    const dec = decision ? `<div class="decision ${decision.toLowerCase()}">${decision}</div>` : '<div class="role">sends noise</div>';
    d.innerHTML = `<div class="name">${role}${isTraitor?' <span class="badge t">TRAITOR</span>':' <span class="badge">LOYAL</span>'}</div>${dec}`;
    wrap.appendChild(d);
  };
  card(0, 'Commander', false, order);
  lieutenants.forEach(L => card(L, fmt('General %L%', { L: L }), traitorSet.has(L),
    traitorSet.has(L) ? null : decisions[L]));

  const loyalDecisions = Object.values(decisions);
  const agree = loyalDecisions.every(v => v === loyalDecisions[0]);
  const correct = agree && loyalDecisions[0] === order;
  const s = $('status');
  if(n > 3*f && correct){
    s.textContent = fmt('✓ All %length% loyal generals agreed on %order%. n=%n% > 3×%f% — consensus holds.', { length: loyalDecisions.length, order: order, n: n, f: f });
    s.className = 'status ok';
  } else {
    s.textContent = fmt('✗ Consensus failed: with n=%n% and %f% traitors, n is not > 3×%f%. Loyal generals split.', { n: n, f: f });
    s.className = 'status bad';
  }
  console.log('n=',n,'f=',f,'loyal decisions:', loyalDecisions, '| n>3f:', n>3*f, '| agreed&correct:', correct);
}

$('run').addEventListener('click', run);
run();
Result
Console

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).

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/byzantine-generals/Content licensed under CC BY-NC 4.0.