← The Books

Agreeing Among Liars

Can machines agree when some of them may lie, telling one thing to one and something else to another? How many honest machines does each liar cost?

We find out by exploring how four bandits holding a hilltop, some of whom might lie, agreed whether to hold it or scatter, first by plain word and then under seal.

After Leslie Lamport, Robert Shostak and Marshall Pease, The Byzantine Generals Problem, 1982 · Marshall Pease, Robert Shostak and Leslie Lamport, Reaching Agreement in the Presence of Faults, 1980

At dusk a bandit in a purple cloak stands alone inside a small ring of huge rough stones, three strongboxes and a ladder drawn up against the wall behind them, looking up at the darkening sky
Where this book sits
This book retells
Leads to

Each link is an idea one paper took from another. Point at one, or tap it, to read how.

a paper this book retells a paper retold in another book a paper outside the series

First, in machine terms

Many computers, some of them lying

A group of computers must all follow the same order, though any of them may be faulty in any way at all, and nobody knows which.

A faulty machine may do anything. It may tell one peer one thing and another peer something else, send nothing, or act together with another faulty machine. A machine that receives two accounts that disagree cannot tell which of the senders is at fault. Lamport, Shostak and Pease (1982) worked out what agreement costs under such faults, and found two answers.

  • With plain messages, agreement is possible only if more than two thirds of the machines are honest: it takes 3f + 1 machines to tolerate f traitors.
  • With signed messages that cannot be forged, it is possible whatever the number of traitors.

The first answer prices every faulty machine in honest ones, and the second takes the price away. We tell it with four bandits on a hilltop, their rats, and their seal rings.

Two explanations, one pair of messages

C sends the order
B a peer
A the receiver

A holds two messages. Which machine is faulty, C or B?

The crown of Mount Phyle from the air: a small ring of rough stones on a rocky summit in mist, with three smaller stone rings out on the slopes among pines
The crown of Mount Phyle

Four bandits, out of sight of one another

Bandits hold the crown of Mount Phyle with their loot. Bandit 1, the chief, sits inside a ring wall with no gate, and bandits 2, 3 and 4 keep lookout posts out on the slopes, none within sight or earshot of another.* They send word only by rat, and they have one question to settle.

Only ratsEvery word goes by rat, from one post to one other post, because no man can see or hear another.
Some men lieNobody on the crown dies, and the runs between the posts are short. But some men do not report what they were told.
BelowFour mercenaries camp at the foot of the hill. Their trouble is the opposite one: none of them lies, but any of them may die.*

Each end of the hill has a friend it cannot count on: above, a friend who may be lying, and below, a friend who may be dead. Which of the two is the worse trouble to arrange against is settled once the crown has its arrangement.

One question, two answers

Hold, or scatter

The question is whether to hold or to scatter. The bandits must all hold the hill and keep the loot, or all scatter and abandon it, and what matters is that all four do the same. Half holding while half scatter is worse than either.

Which answer is better is never at issue, and holding ties no man to a post: each holds from wherever they choose. Nobody dies, and no night is told here. What is described is an arrangement, and nothing comes out of it.

Each bandit forms an account of what should be done. The three at the posts have each watched one approach from the slopes. The chief, inside the wall, has seen only sky, and goes by what the chief knows of the loot. The four accounts must reach four heads unaltered, and that is hard, because a liar can send one thing to one man and something else to another.

So take the accounts one at a time. One man, the chief for this round, sends an order to the other three, the guards. Two things are wanted of that sending, and a third point settles who the chief is.

The first condition

Honest guards obey one order

Every honest guard obeys the same order.

The second condition

An honest chief is obeyed

If the chief is honest, every honest guard obeys the order the chief sent.

The chief is a job

Not a rank

Bandit 1 sits inside the ring wall, but whoever's account is going round is the chief for that round.

The chief is a job so that one sending serves for every man's account. Run it four times, once for each account, and every honest man ends holding the same four accounts. After that, any rule the four all apply gives them all the same answer.

The two conditions do unequal work. If the chief is honest, the second condition gives the first for nothing. If the chief lies, the second says nothing at all, while the first still stands: honest men must end up together even when the man they listened to told them different things. That case is the whole difficulty.

A liar may do anything: send different orders to different men, send nothing, keep a lie up, or agree lies with another liar. Nobody on the hill, and no reader, ever learns who the liars are.

Test the two conditions on any case. Choose whose account is going round, suppose one man lies, and set what each guard obeys. Watch which condition fails, and what the second has to say once the supposed liar is the chief.

Test the two conditions suppose, then decide

The chief might lie, so the chief's slip cannot be taken alone. The plain remedy is for each guard to ask the other guards what the chief told them, and to compare. Whether a guard can do that depends on how word travels on the crown.

How word travels

The rats in the wall

Word on the crown travels by rat, and a rat's run here is short and sure. That is why each guard can ask the others what the chief told them, and can count on an answer.

The runs are direct, over the rocks and through the chinks of the wall, and no rat has ever taken longer than a sandglass takes to run. At dusk, before the posts were manned, the four turned their glasses together at one word, and each turns theirs again the moment it runs out. One running of the glass is a round. Within it every man who is going to send, sends, and every slip sent arrives before the glass is empty.

Each man has trained rats to run to each of the others. A man writes a slip, ties it on a cord knotted with their own number to one of the rats, and lets it go. The wall has no gate, but its stones do not fit close, and a rat finds the chinks. Three things are assumed of a rat.

At dusk inside a small ring of huge rough stones open to the sky, three iron-bound strongboxes of loot stand on a low stone shelf against the wall, the last light on its top edge
What a rat gives · first

It arrives as written

A slip that is sent arrives, and it arrives as written.

What a rat gives · second

The knots name the sender

The knots on its cord name the man who sent it, so no man can be impersonated.

What a rat gives · third

Silence can be seen

If nothing comes from a post within the round, then nothing was sent from it.

The first two come with the rats and their cords. The third is the one that costs something. It is bought with the short run and the rounds, exactly what the mercenaries at the foot do not have.* Silence is also given a meaning, or a man could block everything by sending nothing: no slip within the round counts as hold. Hold is the default because some definite answer is needed, and nothing says it is the wiser one.

The view from behind a rough dry-stone breastwork at a lookout post, over a steep wooded slope falling to the sea in dusk light; no wall and no other post in sight

What none of this gives is any check on content. A plain slip says whatever its writer chose, and a guard reporting what the chief sent may write anything at all. The knots show who sent a slip, and nothing shows whether it is true.

Run one round three ways. In the first, every slip arrives. In the second, watch what an empty glass tells bandit 3. In the third, watch what bandits 2 and 4 are left holding.

One round of rats the glass runs out

H on a rat is a slip saying hold, S a slip saying scatter. The chief's order is scatter.

Choose what happens in the round.

So guards can compare notes, and silence means something, but no slip can be checked against what its writer was told. The first test of comparing notes is the smallest party: a chief and two guards, with one of the three a liar.

The smallest party

Three cannot be brought to agree

In a party of a chief and two guards with one liar among the three, comparing notes does not save the two honest men, and nothing else can.

The reason shows from one honest guard's post. Put that guard, bandit 2, in two nights. In the first, the chief is honest and sends hold to both guards. Suppose bandit 3 is the liar, and tells bandit 2 "the chief sent me scatter". The second condition binds bandit 2: the chief is honest, so bandit 2 must hold.

In the second night, suppose the chief is the liar, sending hold to bandit 2 and scatter to bandit 3. Bandit 3 is honest, and reports, truthfully, "the chief sent me scatter". Press the buttons in turn, and compare what bandit 2 holds in the two nights.

Two nights seen from bandit 2's post

First night

Suppose the chief is honest and bandit 3 lies.

bandit 2 holds: nothing yet
Second night

Suppose the chief lies and bandit 3 is honest.

bandit 2 holds: nothing yet

■ hold ■ scatter   A slip's word is what it says the chief sent.

Press the buttons in turn.

Bandit 2 holds exactly the same two slips in each night: hold from the chief, and bandit 3's word that the chief sent scatter. Bandit 2 cannot tell the nights apart, so must do the same in both. The first night demands hold, so bandit 2 holds in the second night too. The same argument, run on bandit 3 against a mirror of the first night, has bandit 3 scatter in the second night. There both guards are honest and have gone two ways, which the first condition forbids.

One distinction is missing at the post. A lying chief and a lying peer leave a guard holding the same two slips, and each calls for a different answer.

That argument is persuasive and not a proof, because reasoning of just this shape has settled things that turned out false. The result is correct all the same, and the panel gives the argument as far as it goes.

Three men cannot bear one liar. What remains to settle is how many men can, and so what a liar costs.

Proof — that three cannot be brought to agree, as far as such an argument goes

The two conditions are the paper's IC1 and IC2, for a commanding general and two lieutenants with oral messages and at most one traitor. A, B and C are three situations defined in the steps. The result is Pease, Shostak and Lamport 1980, whose rigorous proof this is not. Claim. No arrangement of oral messages brings three men, one possibly a liar, to meet both conditions.

  1. Suppose an arrangement works for three men with one liar: all honest men obey the same order, and an honest chief is obeyed.
  2. A. Chief honest, sending hold to both guards; the second guard lies, reporting the chief sent me scatter.
  3. B. Chief the liar, sending hold to the first guard and scatter to the second; the second guard is honest and reports the same words.
  4. The first guard receives the same two things in A and B and nothing else, so the first guard does the same in both. In A the chief is honest, so the first guard must hold, and therefore holds in B.
  5. C, the mirror of A: chief honest, sending scatter to both; the first guard lies. By the same argument the second guard scatters in C, and B looks like C to the second guard, who therefore scatters in B.
  6. In B both guards are honest and have gone two ways, against the first condition.∎
What a liar costs

Four men to a liar

A liar costs more than three men. One liar wants four men, two want seven, three want ten. The crown has four, so it bears one liar and no more.

The price follows from the party of three. Suppose some method brought three men or fewer to a liar safely through. Then three real men, one of them a liar, could each play a third of that method's men in their own heads, none playing more parts than the method bears liars. The method would keep its promise among those parts, and each real man would do what their own parts did. Three real men would then agree against one liar, which cannot happen.

Asking for less does not help. The bandits might settle for acting at about the same time, but that can be turned back into acting at exactly the same time, so the one is as hard as the other.

Press for one more liar and read what plain slips cost in men and in rounds of reports.

The price of a liar press and read

1liars to bear 4men with plain slips 2rounds of reports

The price says only what cannot be done with fewer men. With enough men there is a method that works, the Repeating. It needs one tool, the greater count: any rule that takes the accounts a guard holds and returns one, such that if most of them say the same thing, that is what it returns.

In the Repeating the chief sends an order to every guard, each guard repeats to the other guards what the chief sent, and each guard then obeys the greater count of the accounts at their post. On this crown, bearing one liar, that is two rounds. Scroll to watch it run, once with a guard lying and once with the chief.

1 · Four men

A chief and three guards

Bandit 1 is the chief for this sending, and bandits 2, 3 and 4 are the guards. Each man's line runs outward, and later moments are further out. Blue slips say hold, red slips say scatter.

2 · First round

The chief sends the order

Suppose bandit 3 lies and the chief is honest. The chief's order is scatter, and it goes to each guard.

3 · Second round

Each guard puts it about

Each guard repeats to the other two what the chief sent them. Bandits 2 and 4 repeat scatter. Bandit 3 writes hold to both, which a plain slip allows.

4 · The greater count

An honest chief is obeyed

Bandit 2 holds scatter from the chief, hold from bandit 3 and scatter from bandit 4, and obeys the greater count: scatter. So does bandit 4. The supposed liar's word was outvoted, and an honest chief's order stood.

5 · Another night

Suppose the chief lies

Now the chief sends scatter to bandit 2, hold to bandit 3 and scatter to bandit 4. There is one liar, so all three guards are honest.

6 · Second round

Each guard repeats faithfully

Each guard tells the other two exactly what the chief sent them, so every guard now holds the same three accounts.

7 · The greater count

All three go the same way

Each guard holds scatter twice and hold once, and the greater count is scatter for all. Nobody worked out who lied. The lie was outvoted, which is cheaper.

Either way the honest guards end together, and where the chief is honest they end on the chief's order. The price is steep all the same. Every further liar costs three more men and another round of reports about reports, and the crown has four men. All of that cost comes from one fact, that a plain slip says whatever its writer chose. A slip that could not be altered would cost less.

Proof — that fewer than four men to a liar cannot be made to work

Let n be the number of men and m the number of liars the method is built to bear. The two conditions are the paper's IC1 and IC2. Claim. No method of oral messages brings n men safely through m liars when n ≤ 3m. A method's men are called its parts; the real men play them.

  1. Suppose a method brings n men safely through m liars with n ≤ 3m. Call its men parts.
  2. Set three real men, one a liar, to play the parts: the real chief plays the parts' chief and at most m − 1 of its guards, and each real guard plays at most m of its guards. Since n ≤ 3m, they divide so.
  3. Word between two parts played by one man passes in that man's head; word between parts played by different men goes by rat, and, as the rats above are assumed to give, arrives as sent and correctly attributed.
  4. At most one real man lies, and that man plays at most m parts, so at most m parts lie — which the method was assumed to bear. It therefore keeps both conditions among the parts.
  5. By the first condition, all the parts played by one honest real man obey one order, which that man obeys; by the second, if the real chief is honest then every honest part obeys the real chief's order. So the three real men satisfy both conditions against one liar, which, as we saw, cannot be done.∎
The Repeating, stated formally

The Repeating bearing m liars is the paper's algorithm OM(m); the greater count is its function majority. What it gives. Bearing m liars, it meets both conditions whenever there are more than 3m men and at most m of them lie.

  1. (1) The chief sends an order to every guard.
  2. (2) Each guard takes what was received, or hold if nothing came, and — unless m is zero — acts as chief in turn in the Repeating bearing m − 1 liars, putting that order about to the other guards.
  3. (3) Each guard now holds their own account and one from each other guard, and obeys the greater count of them.
Proof — that the Repeating meets both conditions above the bound

Let n be the number of men, m the number of liars the Repeating bears, k the number of men who actually lie, and v an order. Claim. The Repeating bearing m liars meets both conditions whenever n > 3m and k ≤ m.

  1. Lemma. Bearing m liars, the method meets the second condition if there are more than 2k + m men and at most k liars. By induction on m: for m = 0 an honest chief's order arrives as sent. Assume it for m − 1.
  2. An honest chief sends v to all n − 1 guards. Each honest guard puts v about among n − 1 men bearing m − 1 liars, and n − 1 > 2k + (m − 1), so by the hypothesis every honest guard receives v from every honest guard.
  3. Since n − 1 > 2k, most guards are honest, so v is most of what each honest guard holds and the greater count returns it.
  4. The theorem, by induction on m. If the chief is honest, the lemma with k = m gives the second condition, and the first follows from it.
  5. If the chief lies, at most m − 1 guards lie, and there are more than 3m − 1 > 3(m − 1) guards, so the hypothesis applies to their repeatings: for each guard, any two honest guards end holding the same account of what that guard put about.
  6. So any two honest guards hold the same accounts in the same places, and the same greater count of them. The first condition holds; the second is vacuous, the chief being a liar.∎
A slip that cannot be altered

The seal rings

A slip that cannot be altered is made with a seal ring. Each man on the crown has a signet cut with their own number. A slip sent under seal is written in wax and stamped, and a man passing it on stamps their own seal beside the last.

So hold : 1 : 2 is the chief's order to hold as relayed by bandit 2, and the line of stamps names every hand the slip has passed through. What a seal can and cannot do is short.

A seal · first

It cannot be counterfeited

An honest man's seal cannot be counterfeited, and tampering shows.

A seal · second

Anyone can read it

Anyone can tell whose seal is whose.

A seal · not assumed

A liar's seal, or a refusal

Nothing is assumed about a liar's seal, since liars may lend each other rings. A seal also cannot compel. A man can refuse to pass a slip on, and simply cannot alter it.

A seal therefore shows what an honest man stamped, and that is enough for a new method, the Sealed Repeating. Each guard keeps a sheaf of the orders properly received, and a fixed standing rule turns a sheaf into one order, with an empty sheaf giving hold.

The chief seals an order and sends it to every guard. A guard given a properly sealed order not yet in the sheaf puts it in. If fewer guards' seals stand on it than the party is built to bear liars, the chief's not counted, the guard adds their own seal and sends it to every guard not already named on it. When no further slip can come, each guard obeys the standing rule applied to the sheaf. The passing on is what makes it work: an order that reaches one honest guard reaches every honest guard, so their sheaves hold the same orders, and equal sheaves give equal answers.

Three men are now enough. If the chief lies, sealing hold to one guard and scatter to the other, each guard passes theirs across, both sheaves hold the same two orders, and the same standing rule sends both guards the same way. Each guard also now holds two orders under the chief's seal, which could not both exist if the chief were honest. The chief has convicted themselves, of lying and of nothing else, and only because the chief was careless enough to seal two orders.

The price of a liar falls with it. Under seal a party bears any number of liars, so long as it has at least two men more than it has liars, because with fewer honest men agreement would mean nothing.

Try it on the crown's four men. Suppose any of them lie, choose what a lying chief seals, and read the sheaves. Watch whether the honest guards end on one order, and whether a sheaf comes to hold two orders under the chief's seal.

Seal and pass suppose, then run it

■ hold ■ scatter   The standing rule used here is an example: one order in the sheaf gives that order, and anything else gives hold. In this picture a supposed liar guard only withholds. That is one thing a liar may do, not the worst. An honest chief seals scatter.

Under seal any number of liars can be borne, whatever the size of the party. Only the question gives out: with fewer than two men more than there are liars, too few honest men remain for agreement among them to mean anything. Where plain slips bought each liar with three more men, seals buy each with one more glass.

The crown can agree, then, by plain slip or under seal. The camp at the foot of the hill has its own trouble, and the two ends can now be set side by side.

The Sealed Repeating, stated formally

The Sealed Repeating bearing m liars is the paper's algorithm SM(m); a seal is its unforgeable signature (assumption A4), and a sheaf is the set Vi held by guard i. The standing rule is its function choice. A slip hold : 1 : 2 is the paper's v : 0 : j1, with the chief's seal first.

  1. (1) The chief seals an order and sends it to every guard.
  2. (2) A guard given a properly sealed order not yet in the sheaf puts it in; and if fewer than m guards' seals stand on it — the chief's not counted — the guard adds their own seal and sends it to every guard not already named on it.
  3. (3) When no further slip can come, the guard obeys the standing rule applied to the sheaf.
Proof — that the Sealed Repeating works against any number of liars

Let m be the number of liars the method is built to bear, i and j two honest guards, and k the number of guards' seals standing on a slip, the chief's not counted. Claim. Whatever the number of men, if at most m lie, both conditions hold. A sheaf is the set of orders a guard has put in.

  1. Second condition. An honest chief seals one order and sends it to all, and no one can counterfeit that seal, so every honest guard's sheaf holds exactly that order and the standing rule returns it.
  2. First condition. Take the chief to be a liar. It is enough that if an honest guard i has an order in the sheaf, every honest guard j has it too; equal sheaves give equal answers.
  3. If i received it under the chief's seal alone, i sealed it and sent it to every other guard, so j has it.
  4. If it reached i carrying k guards' seals and j is among them, j had it already.
  5. If j is not among them and k < m, then i seals it and sends it to every guard not named on it, j included.
  6. If j is not among them and k = m: the chief is a liar, so at most m − 1 guards lie, so one of the m named on the slip is honest — and that guard, on first receiving the order, sent it to every guard not then named on it, j among them.
  7. Nowhere were the men counted. The bound of four men to a liar belongs to unsealed slips, not to lying, and the seals dissolve it.∎
The two ends of the hill

The two halves

Set side by side, the two ends of the hill come out very differently. Above, agreement is had in a few rounds: four men bear one liar by plain slip, and under seal any number of liars is borne.

Below, where no man lies but any man may die, and no bird has a longest flight, no arrangement whatever guarantees that anybody ever moves.* The bandits are no cleverer than the mercenaries. The bandits have rounds to bound the runs between them, and the mercenaries have nothing of the kind. Each end is short of exactly one distinction, and it is the same shape of trouble twice over.

Mount Phyle from the air: a steep wooded crag with a ruined wall on its top, and a few red-roofed houses among the pines on the slopes
Below

A dead man or a bird in a pine

A man with an empty perch cannot tell whether the man in that tent is dead or whether the bird is in a pine. So the man can never safely stop waiting, and nothing is ever concluded.

Above

A lying chief or a lying peer

A guard holding two accounts of one order that disagree cannot tell whether the chief lied to one of them or the peer is lying to them. So no single man's word can ever be trusted, and nobody ever learns who lied.

In both cases what is lost is smaller than it looks. Below, nothing goes wrong: the men are never in disagreement, only never finished. Above, nothing is discovered: the men agree, and are wrong together as readily as right together. No arrangement on the hill tells anybody who failed. Each is built so that nobody needs to be told.

The worse trouble, then, is the one without a clock. Lies can be outvoted when silence means something, because every word that is going to come has come by the end of the round. A death cannot be told from a delay when silence never means anything.

Back to machines

The crown was a group of machines

Read the crown again with machines at the posts. Every bandit is a machine that may be faulty in any way, every slip a rat carries is a message, and a seal is a signature that cannot be forged. Hover over a row, or tap it, to see who is who.

On the crown
In the machine room

With plain messages, machines can agree despite liars only if more than two thirds are honest. With unforgeable signatures, they can whatever the number of liars.

Nothing in either tells anybody which machine lied, except a commander who signs two contradictory orders. All of it rests on detecting silence, which in practice means bounded message time and clocks kept in step.

The Crown of Mount Phyle, in detail All the papers

Setting The Crown of Mount Phyle

The papers behind this book

The papers behind this book. Leslie Lamport, Robert Shostak and Marshall Pease, “The Byzantine Generals Problem,” ACM Transactions on Programming Languages and Systems 4, 3 (July 1982), 382–401; and Marshall Pease, Robert Shostak and Leslie Lamport, “Reaching Agreement in the Presence of Faults,” Journal of the ACM 27, 2 (April 1980), 228–234, for the rigorous proof that three cannot be brought to agree.

The bandits go by number, not by name: bandit 1 is the chief inside the ring wall and bandits 2, 3 and 4 hold the posts. The mercenaries at the foot are numbered separately, so the bandits' bandit 1 is not the mercenary in tent 1.

The ideas. A commander must get an order to n − 1 lieutenants so that IC1 all loyal lieutenants obey the same order and IC2 they obey the commander's order if the commander is loyal. IC2 gives IC1 only when the commander is loyal, which is not assured: that is the problem. With oral messages no solution exists for three generals against one traitor, because a loyal lieutenant cannot distinguish a lying commander from a lying peer; more generally nothing works below 3m + 1 generals, shown by having three generals each simulate a third of a hypothetical smaller solution, and settling for approximate agreement does not help, since it can be turned back into exact agreement. Above the bound, OM(m) works: the commander sends a value, each lieutenant relays what was received by OM(m − 1), and each takes the majority — one extra round per traitor tolerated. Unforgeable signatures change everything: SM(m) tolerates any number of traitors with no requirement at all on the number of generals, and three generals suffice against one. No assumption is made about a traitor's signature, so signatures prove what the loyal did and nothing about the rest, and a traitor can still withhold a message. What no algorithm gives is identification, the sole exception being a commander who signs two contradictory orders. And all of it rests on A3 — detecting absence — which in practice means bounded message time and clocks kept synchronised, itself a problem as hard as this one.

Lamport, L., Shostak, R., and Pease, M. The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst. 4, 3 (1982), 382–401.

Pease, M., Shostak, R., and Lamport, L. Reaching agreement in the presence of faults. J. ACM 27, 2 (1980), 228–234. The rigorous impossibility proof for three.