How can computers agree when some of them might be lying?

With enough honest voices, and better still with signatures. Researchers proved that when nobody can prove who sent a message, a group can reach reliable agreement only if it has more than three times as many members as liars: at least 3n+1 participants to survive n of them. If messages carry digital signatures, 3n is enough. The liar here is what computer scientists call a Byzantine fault: a component that shows different symptoms to different observers, so the others can't even be sure whether it has failed.

The question came up in 1978 in SIFT, a NASA-sponsored project at SRI International built on the idea of several general-purpose computers messaging each other to reach a consensus, even if some of them were faulty. To make it easier to understand, Leslie Lamport dressed it up as an allegory of generals surrounding a city. They must decide as a group whether to attack or retreat, and all must agree, since a half-hearted attack by only some of them would be worse than either a coordinated attack or a coordinated retreat. The trouble is that a traitor can lie selectively: with four generals favoring attack and four favoring retreat, a ninth, disloyal general can send a retreat vote to one camp and an attack vote to the other, splitting the army.

Robert Shostak, who first formalized the problem, showed that at least 3n+1 participants were needed, and his colleague Marshall Pease proved that figure was both necessary and sufficient for any number of faulty participants. Leslie Lamport later showed that with digital signatures, 3n suffice: being able to prove who really sent a message lets a system get by with fewer participants.

The allegory's name has its own small story: the generals were originally cast as commanders of the Albanian army, before being renamed "Byzantine" at a colleague's suggestion, to head off any risk of giving offense. The work earned its authors the 2005 Edsger W. Dijkstra Prize.