Can machines always agree when one of them may stop silently and messages take any time at all?
We find out by exploring how four mercenaries at the foot of a hill, unable to see one another, tried to agree whether to attack or hold when any of them might be dead.
After Michael J. Fischer, Nancy A. Lynch and Michael S. Paterson, Impossibility of Distributed Consensus with One Faulty Process, 1985
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
A group of computers must all settle on the same one of two values, and the value must depend on what the machines started with.
Two things stand in the way. A message may take any time at all: every message arrives, but no delay is too long to be possible. And one machine may stop at any moment, without a word. A machine that hears nothing cannot tell which has happened.
We tell it with four mercenaries, their ravens, and a hill they must take together or not at all.
A has asked B for its value and is waiting for the reply.
Four mercenaries are camped at the foot of Mount Phyle, one to a tent, out of sight of one another and under nobody's command.* Bandits hold the top of the hill, and the four have one question to settle about it.
The question is whether to attack the hill or to hold, and the four mercenaries must all give the same answer. Attacking, they climb together. Holding, each man guards the path down one gully and the hill stays closed. Half attacking while half hold is worse than either: too few to climb, and a hill left open.
Each man formed an opinion at dusk, attack or hold, from what could be seen of that man's own quarter. A man commits by leaving the tent, to climb with the others or to guard a gully, and will not be back before dawn. The four want three things of whatever plan they follow.
Nobody attacks while another holds.
What they do must depend on what they saw.
Sooner or later at least one man leaves the tent.
The second demand shuts out the plan of holding whatever anyone saw, which keeps the first demand and makes the evening pointless. The third shuts out the plan under which nobody ever moves, which keeps the first two for free. One more condition binds the four: they may not draw lots. Each man acts on what has arrived at that man's tent and nothing else.
Two plans come to mind at once. Try each on the sightings below, then try the second again on a night when tent 3 stays silent, and watch which demand is given up.
The hill from above. The badge beside each tent is what that man saw at dusk: A for attack, H for hold.
Each easy plan keeps two demands. Find the one it gives up.
Waiting for every report keeps all three demands while every man answers, and nobody lies at the foot, so it looks like a sound plan. What it gives up shows only when a tent stays silent, and the reason lies in the birds.
The birds can be trusted in every way but one. The ravens always arrive, they bring exactly what was written, and they come in no particular order. But they take as long as they take.
A raven may sit in the wooded gullies for an hour or for the night, so no hour comes after which a man can say that nothing more is on its way. A man may always walk to the perch and find nothing there, and that is not news.
Now add that any one of the four may be killed, and that a dead man's tent simply falls silent. A man waiting on a tent that has not answered is then in one of two situations. Wait at tent 2's perch below, and see whether the hours tell them apart.
Suppose the man at tent 1 is dead. No bird will ever come.
Suppose tent 1's man is well. The raven went out hours ago and is sitting in a pine.
Tent 2 has heard nothing from tent 1. Which night is this?
Both nights look like an empty perch, and waiting longer never turns one into the other. So a plan cannot wait for every report: whenever one man is dead it waits for ever, and can never learn of the death. Each man must act, at some point, without hearing from everyone.
Somewhere in the night, then, the matter gets settled without everyone having been heard. The chance that one tent falls silent is enough to force that, and the next thing to say is when it happens.
Saying when the matter is settled takes three words that ordinary speech lacks.
A position is what each of the four men holds in mind, together with every raven aloft and not yet taken in.
An arrival is the only kind of thing that happens. Going to the perch and finding nothing counts as a turn, and changes nothing.
A position is open if the night can still end in holding and can still end in attacking. A position is closed if only one answer remains.
Open does not describe what anyone thinks. It says only that the answer still depends on the order in which the birds arrive. Once any man has committed, the position is closed, so the matter is settled wherever the night stops being open.
The first tool of the argument is about that order. Below, let one pair of tents trade ravens first, start the night again, let the other pair go first, and compare how the night stands at the end.
Each line is one tent, at one moment after another, and each ring further out is later. A raven is an arc from one tent to another. A hollow dot is a man who has not committed.
Tents 1 and 2 have ravens to trade, and so have tents 3 and 4. Which pair goes first?
Two runs of arrivals with no man in common do not interfere: run either first, and the night arrives at the same position. The reason is that an arrival is one man taking in one raven and perhaps writing more. All of that belongs to the one man or to the air, and none of it to anybody else.
With these words the question has a sharper form. At dusk every man has a sighting and no bird has flown. The first thing to find out is whether the night is closed already, by the sightings alone.
In the paper's terms a position is a configuration, an arrival an event, a course a schedule, a fair course an admissible run, and open and closed are bivalent and univalent. Lemma 1. Let courses σ₁ and σ₂ both be applicable at a position, and let the set A of men who act in σ₁ and the set B of men who act in σ₂ be disjoint. Then each can be run after the other, and both orders reach the same position.
The sightings at dusk do not always close the night. To see why, line up some possible beginnings so that each differs from the next in one man's sighting, with all-hold at one end and all-attack at the other.
Suppose every beginning in the row were already settled by the sightings alone. The second demand forces the two ends opposite ways. The three in between are yours to settle. Click a beginning to change it, and watch the two that are marked.
However the row is settled, two neighbours split, and the supposition fails. Nobody died to make that argument work. The other three could not tell a silent man from a slow one, and so could not tell two different beginnings apart. However the four arrange their affairs, the sightings can fall so that the night begins open.
The night can begin open, then. It still seems that it cannot stay open for ever, and that some arrival, sooner or later, must be the one that closes it.
In the paper's terms a position is a configuration, an arrival an event, a course a schedule, a fair course an admissible run, and open and closed are bivalent and univalent. A beginning is an initial configuration: the four sightings, with no raven yet aloft. Lemma 2. Whatever the four have arranged, some beginning is open.
No arrival has to be the one that closes the night. Whichever raven would have settled the matter, the night can go on without it for a while, then take it in, and be open still.
The raven is never kept from landing, because the birds are reliable. The argument asks only whether its landing must settle anything. Scroll slowly, and the picture moves with you.
The night stands open: it can still end either way. One raven is waiting to be taken in. The birds are reliable, so it will land. What is in doubt is whether it must settle anything when it does.
The top row is the night going on while that raven waits, one arrival at a time. Under each position is the position once the raven lands there.
Then every position in the bottom row is closed, for holding or for attacking. Both must appear, because the night at the top could still end either way.
Two positions in the top row are one arrival apart. Land the raven at the first and the night is settled for holding. Land it at the second and the night is settled for attacking.
If that one arrival is another man's business, it and the raven are separate folds: either order reaches the same position. So one more arrival leads from a night settled for holding to a night settled for attacking. That cannot be.
If both arrivals are one man's business, let that man go quiet, as a man does whose birds are in the pines. The other three must finish without the quiet man. From where they finish, the raven alone still leads to holding, while the quiet man's other arrival and then the raven still leads to attacking. A finished night would still be open. That cannot be either.
The supposition fails. Somewhere in the bottom row a position is open. No single raven is ever the one that has to settle the matter.
Whatever arrives while the raven waits is either another tent's business, so that the order cannot matter, or the same tent's, and then that man can go quiet and the rest cannot tell which landed first. Two facts are now in hand: the night can begin open, and no single arrival need close it. What is left is to see the night they make when both are used without rest.
In the paper's terms a position is a configuration, an arrival an event, a course a schedule, a fair course an admissible run, and open and closed are bivalent and univalent. Lemma 3. Let C be an open position and e an arrival applicable at C. Let 𝒞 be the set of positions reachable from C without allowing e, and 𝒟 the set got by allowing e at each position of 𝒞. Then 𝒟 contains an open position.
Used without rest, the two facts make a night that is entirely fair and never closes. Start from a dusk that leaves the night open, keep the four men in a queue, and let whoever orders the arrivals choose each one so that the night is open after it.
The man at the head of the queue takes in the raven longest aloft for that tent, or walks to the perch and back if none is waiting, and then goes to the back of the queue. Every man's turn comes round again and the oldest raven is always taken first, so no man is starved of a turn and every raven is taken in at last.
Let the night run, and watch the count of men committed. Then give the birds a longest flight, and watch it again.
No man is starved of a turn, and every raven is taken in at last.
The picture shows the pattern of the argument, not a worked plan: the turns and the ravens are real, and that the night stays open is what the two facts guarantee for any plan the four could have made.
Run for ever, that night is entirely fair, and at every stage of it nothing has been settled. The same night can be arranged against any plan the four could have made, however ingenious.
Nobody dies in it. The one death the argument allowed was spent on the reasoning and never on the hill. What limits the four is the possibility of a death, which looks exactly like a slow bird.
Nothing goes wrong. Nobody commits to a wrong answer, because nobody commits at all.
One would have been enough. The demand was only that somebody commit, and even that fails.
The hill has nothing to do with it. The same conclusion holds for any number of men from two upward and any two answers.
The night ended differently once the birds had a longest flight. That shows where to look for what the four would need.
What the four would need is some way to tell a dead man from a slow bird. Slow birds alone are no trouble, and neither are birds that arrive out of order. The trouble is two things together: no longest flight, and a dead man looking exactly like a slow bird. Three changes would each take it away.
Give the birds a longest flight, and enough silence means something.
The report must in the end name every dead man, and in the end stop naming at least one living one. Such a report is enough while more than half live.
If no man can die once the evening has begun, a majority can manage.
None of the three is on offer at the foot of the hill. The first is on offer at the top, where the bandits' rats have a longest run.*
Read the camp again with machines in the tents. Every tent is a process, every raven is a message, and a tent that falls silent is a machine that has stopped. Hover over a row, or tap it, to see who is who.
When messages may take any time and even one machine may stop, no protocol can guarantee that the group ever decides.
Agreement itself is never broken. What cannot be promised is an end to the waiting.
Practical protocols live with this by changing the rules a little: delays that are bounded in the end, an imperfect report of who has failed, or a coin.
Setting The Foot of Mount Phyle
The paper behind this book. Michael J. Fischer, Nancy A. Lynch and Michael S. Paterson, “Impossibility of Distributed Consensus with One Faulty Process,” Journal of the ACM 32, 2 (April 1985), 374–382.
The ideas. No deterministic protocol can guarantee consensus in an asynchronous system in which even one process may crash. The proof turns on bivalence: a configuration from which both decisions are still reachable. There is always a bivalent initial configuration, and from any bivalent configuration the step that would resolve the indecision can be deferred and then taken without resolving it — so a scheduler can build an admissible run that never decides. Three details carry the weight: the run the proof constructs contains no failure at all, the single permitted fault being spent on the argument; agreement and validity are never violated, only termination is lost; and the result bites even though the requirement is merely that some process decide. The obstruction is not slowness but the inability to distinguish a crashed process from a slow one. Relax it — bound the delays, even only eventually, or supply an imperfect oracle about who has failed — and consensus becomes solvable again; the paper's own §4 relaxes it by letting processes die only before the protocol begins, and gives a protocol that works whenever a majority are sound.
Fischer, M. J., Lynch, N. A., and Paterson, M. S. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (1985), 374–382.
Dwork, C., Lynch, N., and Stockmeyer, L. Consensus in the presence of partial synchrony. J. ACM 35, 2 (1988), 288–323.
Chandra, T. D., and Toueg, S. Unreliable failure detectors for reliable distributed systems. J. ACM 43, 2 (1996), 225–267.