Can the loyal generals ever be certain they will act as one? The story above hides two different problems, and computer scientists study them separately. In the first, called the Two Generals problem, everyone is honest but riders can vanish. In the second, every rider gets through but someone is lying; that is the Byzantine Generals problem itself. Both have surprising answers. We’ll take them one at a time, but first, the rules.
Puzzle 1 · The lost messenger
Start with just two generals, A and B, both completely honest. A wants to attack at dawn, but only if B attacks too. The only danger is the valley between their camps: a rider sent across it can be captured, and his general never finds out.
Predict
General A sends “Attack at dawn.” General B sends back “Got it.” Both riders happen to get through, but each general knows only about the rider who reached him. Can each general now be certain that the other will attack?
(c) is right, and it surprises most people. B sent the last rider, so he can’t know whether “Got it” arrived. If it was captured, A would still be wondering whether B ever got the order, and might hold back. So B can’t be sure A will attack.
For (a): A did get the confirmation, but B can’t know that, and a general who isn’t sure his partner will attack may hold back. So A can’t fully count on B either. For (b): the extra confirmation can be captured too, and then A is the one in doubt. Whoever sends the last rider is always unsure. Scroll on to watch it happen.
Puzzle 2 · The liar
Now flip the danger around. We’re back to three generals, but this time the roads are safe.
Predict
Now every messenger arrives, but one of the three generals might be a traitor who lies. The two loyal generals can send each other as many messengers as they like. Can they always end up doing the same thing?
(c). That surprises almost everyone; the 1982 paper that named the problem calls it “deceptively simple” and the result surprising. Two-against-one only works if you know which one is the liar, and as the next section shows, a loyal general can’t. For (b): the loyal generals don’t know who the traitor is, so their plan has to work whoever it is, including the commander.
Here is how one traitor beats two loyal generals. Put yourself in one lieutenant’s boots.
Now add a third lieutenant, and keep the same moves. The commander sends his order to each lieutenant. Each lieutenant then sends the other two a messenger reporting the order he got. Finally, each lieutenant goes with the majority of the three versions he now holds. Walk through two cases, then put on the traitor’s mask yourself.
However you play the traitor, the loyal lieutenants agree. A lying lieutenant is outvoted by two true copies of the order. A lying commander can send different orders to different lieutenants, but because the others relay honestly, every loyal lieutenant ends up holding the same three values, so they all reach the same majority.
That turns out to be a general rule. When a liar can put anything he likes in a message, agreement can be guaranteed only if more than two-thirds of the generals are loyal. Three generals with one traitor falls short; four is enough.
Call the number of traitors f and the number of generals n. For the loyal generals to be guaranteed to agree, no matter what the traitors do, you need:
n ≥ 3f + 1
| Traitors (f) | Generals needed (n) |
|---|---|
| 1 | 4 |
| 2 | 7 |
Apply
A system has 10 computers, and they send ordinary messages, so a liar can claim anything. At most how many of them can be traitors, with agreement still guaranteed?
(b) 3. You need more than two-thirds loyal. With 3 traitors, 7 of 10 are loyal (70%). With 4 traitors only 6 of 10 are (60%), and that’s not enough. In the rule’s terms, 10 computers ≥ 3 × 3 + 1.
“Just under half” is the voting instinct, but a traitor doesn’t cast one honest vote: he can tell different people different things, and that’s why a plain majority isn’t enough. For (c) and (d): one traitor needs only 4 generals, and with 10 there’s room for more.
The way out
This puzzle came out of NASA-funded research into making computers reliable enough to fly airliners. Engineers have never beaten the impossibility. Instead, they change the rules of the game, in one of three ways.
Predict
A crypto fan says: “Bitcoin solved the Byzantine Generals problem. Once your payment is confirmed, it’s mathematically impossible to reverse.” Which version is accurate?
(b). Bitcoin didn’t beat the impossibility. It changed the question from “certain” to “overwhelmingly likely”. In the original paper’s numbers, an attacker with 10% of the computing power has about a 0.09% chance of reversing a payment that’s 5 blocks deep, and waiting longer makes it smaller but never zero.
For (c): the protection is real and grows fast. It just isn’t absolute. Every escape route works this way: it changes an assumption rather than breaking the rule.
If messages can be lost, two sides can never be certain they agree. Every confirmation needs another.
If messages arrive but someone may lie, agreement is guaranteed only when more than two-thirds are loyal: 4 generals to survive 1 traitor.
Real systems don’t beat these limits. They change the rules: unforgeable signatures, deadlines, or “almost certain.”
So can the generals ever be certain? Only by changing the rules of the game, and only for as long as those rules hold.