Three armies surround a city. If they all attack together, they win; if they all retreat, they live. If they split, the ones who attack are wiped out. Their only way to talk is to send riders through enemy lines.
Puzzle 1 · The lost messenger
Everyone is honest. Messengers can vanish.
Puzzle 2 · The liar
Every messenger arrives. Someone lies.
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.
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.
Answer the question above to start.
A’s rider gets through, so B knows the plan. But A has no way to know that. For all A can tell, his rider is lying in a ditch.
So B sends a rider back with “Got it.” When it arrives, A can relax. Now B is the one wondering whether his rider made it. If it didn’t, A may hold back, and B would attack alone.
So A sends a rider to confirm the confirmation. Now B can relax, and A is the one left wondering. See the pattern?
Your turn. Tap Send another rider as often as you like. Can you find the rider that ends the doubt?
There isn’t one. Whoever sends the last rider can never know that it arrived, so certainty would take an endless chain of confirmations. This was the first problem in computer communication to be proven unsolvable.
Real networks, including the internet’s TCP protocol, don’t solve it either. They live with it and shrink the doubt, much like sending a hundred riders: failure becomes very unlikely, but never impossible.
Puzzle 2 · The liar
Now flip the danger around. We’re back to three generals, but this time the roads are safe.
Goal 1 Every loyal general does the same thing.
Goal 2 If the commander is loyal, they follow his order.
Without goal 2, “always retreat” would be a cheap win.
The rules: what changes for Puzzle 2
A messenger can be captured on the way. (No longer true.)
Every messenger arrives, carrying his message exactly as it was given to him.
The general who receives a message always knows which camp sent it.
Each general knows when a message is due. If one he’s expecting hasn’t arrived by then, he knows it isn’t coming. That deadline comes back at the end.
Messengers are still the only way to communicate. The danger now is a general who lies.
One general is the commander. He decides, and sends his order by messenger to the other two, his lieutenants.
To double-check, each lieutenant sends the other a messenger saying which order he got. With nobody lying, both attack, and both goals on the card are met.
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.
Answer the question above to start.
You’re Lieutenant 1. The strip at the top shows every message that has reached you, and the two don’t agree. One of the other two generals is lying. Which one?
Maybe Lieutenant 2 is the traitor. Then the commander is loyal, and goal 2 says you must follow his order. You attack.
Or maybe the commander is the traitor, giving each lieutenant a different order. Then Lieutenant 2 is loyal, and is honestly passing on the order he got.
You get the same two messages, word for word, in both worlds, so nothing you receive can tell you which world you’re in. You must attack in the first world, so you attack in the second one too.
Lieutenant 2 is in the mirror image of your spot: the commander’s message to him says RETREAT, and your message to him says the commander said ATTACK. Using the same reasoning you just used, what must Lieutenant 2 do? Think it through, then reveal.
Retreat. From where Lieutenant 2 stands, it looks exactly like a world where the commander loyally ordered RETREAT and Lieutenant 1 is the liar, and in that world goal 2 says he must follow the commander. So in the second world, Lieutenant 1 attacks and Lieutenant 2 retreats. The traitor commander has split the two loyal generals by telling them different things, and neither can catch him.
The trap is symmetry. Each loyal lieutenant is doing the right thing given the messages he has, and that’s exactly what lets the traitor split them.
So in the second world you attack and Lieutenant 2 retreats. The loyal generals have split, and goal 1 fails. Two loyal generals couldn’t outvote one liar, because neither could tell who the liar was. And a smarter rule wouldn’t save them: the full proof shows that whatever rule the lieutenants agree on in advance, one traitor among three can break one of the two goals, either by splitting the loyal generals or by making them disobey a loyal commander.
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 |
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.
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.