If no plan can guarantee agreement when a machine may stop without warning, can chance succeed where planning cannot? What if a machine that is stuck simply tosses a coin?
We find out by exploring how Greek mercenary camps, deadlocked over a plan, let a coin, tossed by each man alone in his tent, break the tie.
After Michael Ben-Or, Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols, 1983
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 one of them may stop without a word.
Every message between them arrives, but no delay is too long to be possible, so a machine that has stopped cannot be told from one whose message is slow. Under those conditions no fixed protocol can promise a decision. One that acts only on what it has received cannot guarantee that the group ever decides, because the order of its messages can always be arranged to keep it waiting.* One idea gets past this.
The coin is the only thing added, and the rest of the problem stays as it was. We tell it with four mercenaries, their ravens and a coin in each tent.
The fixed rule is one example, used only to show the difficulty. The coins fall differently each time.
Four mercenaries camp 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 go by the numbers of their tents.
The four must all attack or all hold. Each formed an opinion at dusk, called a sighting, and committing is final: a man who attacks or holds leaves the tent and its birds for the night.
A silent tent cannot be told from a live one whose bird is slow, and that alone defeats every plan. Nobody lies and nothing goes wrong, and still no arrangement guarantees that any of the four ever commits, because the birds can always be ordered so that the night stays open.* What the four want comes to three demands.
Nobody attacks while another holds.
If all four sighted the same answer, that is the answer they commit to.
Every man who is not killed eventually commits.
The second and third ask more than the impossibility needs. For the impossibility it is enough that both answers stay possible and that somebody commits. Here the second demand says exactly how the answers stay possible: when the sightings all agree the four follow them, which rules out agreeing in advance to hold. The third asks committing of every man left alive. Even the weaker demands could not be guaranteed,* so these cannot be either.
The impossibility rested on one assumption, which is easy to pass over: the four may not draw lots. Each acts only on what has reached them, so that, given the same sighting and the same birds in the same order, each does the same thing every time.
None of the three demands asks for that assumption. Suppose it is dropped and nothing else is changed, so that a man may leave something to chance. The first thing to settle is what chance the four have to hand.
The chance the four have to hand is a coin. Every man at the foot was paid in Attic silver, and every Attic coin has the goddess's head on one face and an owl on the other. Before the tents were pitched the four settled that the owl stands for holding and the goddess for attacking.
A man who cannot settle on an answer, by the rules that follow, tosses a coin high off the thumb, catches it, and favours the answer it shows.
There are four coins and four separate tosses. The four cannot toss one coin together, because nothing on the hill brings them to one place. One man tossing for all would have to send the result by raven, and that raven might be the one still in the pines, or the man might be the one who is killed. So nobody learns another's toss except by bird, if at all. Toss in one tent or in all four, and watch the counts: each tent keeps its own, and no tent's coin follows another's.
Over many tosses owl and goddess come up about equally often. In a short run they need not.
The arrangement asks three things of a coin, and a silver coin tossed high and caught gives all three. A spun coin would not, because it tends to fall to one face, and a struck coin is never quite even.
Over many tosses each face comes up as often as the other.
Each toss owes nothing to any toss before it, in this tent or any other.
Before a toss is made, no one knows how it will fall. After it is made, anyone may know it.
The third matters because of how the arguments of this book treat the birds. Without coins, the birds are taken in the worst order the argument can find: whatever the four arrange, the order of arrivals can be chosen against them.* The same is done here, and done harder. Think of the order in which the birds come down as arranged by someone who can see into every tent, read every strip and see every toss already made, and who arranges the arrivals to keep the four apart for as long as possible.
The one thing this arranger cannot do is see a toss before it is made. The arranger is only the worst case, and no such person exists, but anything that holds against the arranger holds on every night.
Each tent now has a coin that the arranger cannot foresee. The arrangement still has to say when a man tosses, and what the toss then does.
A man tosses at one fixed point in a round, and only when the birds of that round have left the answer open. The arrangement goes in numbered rounds, and every bird carries its round's number, so that a late bird of the second round is not taken for an early one of the third.
In each round each man sends two birds to each of the others, and counts their own two as though they had come. The first is the report: the answer favoured at the start of the round, beginning with the sighting. The second says one of two things: sure of an answer, or unsure. A man may write sure of hold only when the reports read in that round show more than half of all four favouring hold. A round has three steps.
Send the answer favoured now, to all the others.
If all three name the same answer, more than half of all four, send sure of that answer. Otherwise send unsure.
One that is sure of an answer: favour it from now on. Two or more: be settled on it. None: toss the coin and favour the answer it shows. Then the next round begins.
At each step a man waits for three birds, counting their own, and never for the fourth. With four men and at most one silent, three birds always come. A man who waited for four would wait for ever whenever one of them had been killed, and could not know it.
Here is one round as tent 1 reads it. Change what the reports and the second birds say, and watch which of the three endings follows: favouring an answer, being settled on it, or a toss.
Tent 1 has read three reports: its own and two ravens. Press a report to change what it says.
Then three second birds: its own, which the reports decide, and two ravens.
A settled man still has to commit, and committing has a catch. A man who leaves the tent to attack or to hold falls as silent as a dead one, and the others are waiting for three birds each round. If two men committed and a third were killed, the last would wait for ever. So a settled man does one thing more: in the round of settling, at once, both birds of the next round go to all, the report and sure of that answer. This is the rule of parting. Then the man leaves the tent and commits.
The two birds sent early are exactly the two that would have been sent had the man stayed, so the men who remain read nothing different and still get three birds at every step.
Each man now tosses whenever no second bird is sure, alone and unseen, and nothing makes the four coins fall alike. What has to be shown next is that coins falling differently cannot commit two men to different answers.
In the paper's terms the four tents are N = 4 processes, at most t = 1 of which may crash; a sighting is an initial value, a report is the message (1, r, x), sure of v is the D-message (2, r, v, D), unsure is (2, r, ?), being settled is deciding, and a process waits for N − t = 3 messages at each step. The three steps below are the paper's round, written for one process.
One round, r, at one tent.
The same, for N men of whom t may fall silent. Wait each time for N − t birds. Send sure of v when more than N/2 of the reports received name v. Favour v on one sure of v; settle on v on more than t of them; toss otherwise. The arrangement needs N > 2t. On the hill, N = 4 and t = 1.
The rule of parting. A man who becomes settled on an answer in round r at once sends both birds of round r + 1 to all: the report, that answer, and the second bird, sure of that answer. Then the man leaves the tent and commits to it.
This rule is not in Ben-Or's paper. There a process that has decided simply goes on taking part, and nothing is said of stopping. On the hill deciding is committing, and committing is silence, so the rule is needed; the two birds it sends early are exactly the two the man would have sent by staying.
Coins falling differently can never commit two men to different answers. The first two demands hold on every night, whatever the birds and whatever the coins, and the whole of it rests on one small fact about majorities.
In any round, every sure bird names the same answer.
If one man is settled on an answer in a round, every man who finishes that round favours that answer, and every man not killed is settled on it in the next round.
If all four sighted the same answer, every man not killed is settled on it in the first round, and no coin is tossed.
The fact about majorities is the first of the three, and the reason for it is a count. Each man sends one report a round, so a round has at most four reports. A man writes sure of hold only after reading three reports of hold, and sure of attack only after reading three of attack. Three of hold and three of attack out of four must share a man, and a man cannot have reported both.
The other two follow from it. A man is settled only on two sure birds, and every other man misses at most one bird, so each of them reads at least one of the two and favours the same answer. Scroll to watch one round worked out by the rules, with each man missing one of the four birds.
Tent 3 favours attack. Each man will read three of the four reports, and misses one.
Tents 1 and 2 read three reports of hold, and write sure of hold. Tents 3 and 4 each read the attack among their three, and write unsure. A man cannot write sure of attack here, since that needs three of attack.
Tent 1 reads two sure of hold and is settled. Tents 2, 3 and 4 each read one, and favour hold. A man misses at most one bird, so every man reads at least one when two were sent. Nobody tosses.
In the settling round tent 1 sent both birds of the next round: hold, and sure of hold. Those are the very birds it would have sent had it stayed.
Each remaining man reads three reports of hold, writes sure of hold, reads three such birds, and is settled on hold. No bird names attack.
A coin is tossed only by a man who read no sure bird at all, so while anyone is settled, no one is tossing against them. Chance comes into neither result.
The coins cannot divide the four, then, and when the sightings agree no coin is tossed at all. What is left is the night on which the sightings are split and nobody can be sure. On such a night only the coins can bring the four together.
In the paper's terms the four tents are N = 4 processes, at most t = 1 of which may crash; a sighting is an initial value, a report is the message (1, r, x), sure of v is the D-message (2, r, v, D), unsure is (2, r, ?), being settled is deciding, and a process waits for N − t = 3 messages at each step. Claim. If a process decides v in round r, then every process that completes round r adopts v, and every process that does not crash decides v in round r + 1. This is Theorem 1 (iii).
In the paper's terms the four tents are N = 4 processes, at most t = 1 of which may crash; a sighting is an initial value, a report is the message (1, r, x), sure of v is the D-message (2, r, v, D), unsure is (2, r, ?), being settled is deciding, and a process waits for N − t = 3 messages at each step. Claim. If all N initial values are equal, every process that does not crash decides that value in round 1. This is Theorem 1 (ii).
On a split night the coin does its work in the rounds where nobody is sure. Here is one way such a night can go, with tent 4 silent from the start, so that every wait is for the three who remain.
The sightings were hold at tent 1, attack at tent 2 and hold at tent 3. The tosses below are the ones of this night in the story, and the rounds are worked out by the rules. Press through the rounds, and watch for the one in which the tosses happen to agree.
While the reports are split no man may be sure, and each tosses alone. Once the tosses happen to agree, every report of the next round is the same, and that round settles all of them.
The tosses did not have to agree with anybody's sighting. Tent 3 sighted hold and tossed the owl, tent 1 sighted hold and tossed the goddess. That is allowed, because the second demand speaks only of nights when all four sightings agree.
Round 2 settled nothing, though two of the three favoured attack. A man is sure only when more than half of all four agree, and more than half of those heard from is not enough. That keeps one sure answer a round true when a slow bird may be carrying the fourth report.
Nothing is to be read into which answer the coins chose. The coins pick an answer the way the birds' order would otherwise have picked it: by nothing anyone can know in advance. The night could as well have ended in attack.
That night ended in three rounds because the tosses of round 2 fell alike. Nothing made them fall alike, and a night whose tosses keep falling split has no such round. So whether every night ends needs an argument of its own.
An ending cannot be promised on every course of birds and coins. The example could have taken thirty rounds, and there is a course, one among very many, in which it never ends: the tosses keep coming up split, round after round, for ever.
What can be promised is that such courses, taken together, have no chance whatever of happening. With at most one of the four silent, and however the birds are ordered, the chance that every man not killed eventually commits is one. Choose the sightings and run night after night: the number of rounds changes with the coins, and no round can be named in advance.
Choose what each tent saw at dusk. The birds here arrive in a random order, each man missing one of the other three, which is gentler than the arranger would be.
Press to run a night.
The reason is that the coins keep giving the four a way out, and the birds cannot shut it for good. In any round at most one answer can be the subject of sure birds. If every man who tosses comes up with that answer, or, when there is none, all with the same answer, then every man starts the next round favouring one answer, and the next round settles everyone. The arranger can make that harder, round by round, but a way out that keeps coming back with some chance is taken in the end with chance one.
No night can be named by which the four will have committed. There is no round after which committing is certain, only a chance, growing towards one, that it has happened by then. No figure for how fast it grows is given here. A man who asks will we have committed by the fortieth round? can only be told almost certainly. The courses that never end still exist. They have been given no chance at all, and they have not been abolished.
The short argument for this has a gap, said plainly in the panel below, and a full proof came much later.
So the endless courses are still there, and the impossibility said only that such courses exist. Setting the night with coins beside the night without them shows exactly what the coin changed.
In the paper's terms the four tents are N = 4 processes, at most t = 1 of which may crash; a sighting is an initial value, a report is the message (1, r, x), sure of v is the D-message (2, r, v, D), unsure is (2, r, ?), being settled is deciding, and a process waits for N − t = 3 messages at each step. A local coin is step 3(c): set the value to 0 or 1 with probability 1/2 each. g is a value, defined in step 1 below. Claim. With N > 2t, every process that does not crash decides with probability 1. This is Theorem 1 (i), which the paper states without proof.
Is the sketch airtight? No, and it should be said plainly where it fails. Step 1 treats the answer g as fixed before the round's tosses. But a slow man's report for round r comes from how that man's round r − 1 ended, and the arranger chooses which second birds are read there, and may choose after seeing some tosses of round r. So the answer named sure in round r can be picked against the early tosses, and the one-in-sixteen of step 3 is not a bound anyone has proved. Ben-Or's paper states its theorems without any proof. A proof that closes every such gap was published only in 2012, by Aguilera and Toueg; it comes to the same conclusion by a longer road.
What is not claimed? No night can be named by which the four will have committed. There is no round after which committing is certain; there is only a chance, growing towards one, that it has happened by then. Ben-Or's paper gives no figure for how fast that chance grows, and this book gives none.
What the coin changed shows in how the endless night is built. Without coins it takes three steps:* a way for the sightings to fall that leaves the night open; from any open standing, an arrival that can be deferred and taken without closing the night; and so an arranger who defers well can keep it open for ever.
Every step leans on the four being unable to draw lots. Given the same birds in the same order, each man does the same thing, so the arranger knows, before choosing an arrival, what it will lead to. A coin takes that knowledge away.
At a toss the night forks, one way for the owl and one for the goddess, and the fork is taken by the coin. The arranger can still be as clever as before about the birds, and cannot steer both forks at once.
Fix every toss in advance and the argument without coins runs unchanged.* What has changed is that an endless course now needs the coins to cooperate, round after round, and they do not.
The result without coins stands: no arrangement guarantees that anybody ever commits, and this one does not either. It guarantees that the four never commit differently, and that failing to commit has no chance at all. The difference between every course and probability one is the whole of what the coin bought.
Three things would change matters at the foot of the hill: a longest flight, or some report of who has died, or all the deaths happening before the evening begins.* The coin is a fourth way, and a different kind. The other three give the four men more knowledge of the world. The coin gives them none. It gives the world less power over them.
The world keeps some of its power all the same. The coin has limits, and the first of them is how many of the four may fall silent.
The number of the silent is the first limit. The coins cannot carry the four past two silences. The arrangement needs the silent to be fewer than half, and that is no weakness of this arrangement, since every other shares it.
Half is too many. If half the men or more may fall silent, no arrangement, with or without coins, can meet all three demands: that no two commit to different answers, that matching sightings are followed, and that every man not killed eventually commits. With half or more silent, the order of the birds can imitate a hill split in two. Hold back the birds of one pair of tents and then of the other, and watch what each pair is bound to do.
The picture shows the pattern of the argument, not a worked plan. Nobody falls silent in it: every bird is only late.
Each pair hears only itself, and must commit as though the other pair were dead, because for all it can tell they are. The pairs sighted differently, so they commit differently, and no coin can help: whatever the coins show, each pair reads exactly what it would read on a night when the second demand binds it.
In the paper's terms this is the case N ≤ 2t, here N = 4 and t = 2, a process being able to crash at any moment. Claim. No protocol, randomized or not, meets agreement, validity when all inputs are equal, and termination for every process that does not crash. This is the remark after Theorem 1: the schedule can simulate a partition.
Four tents bear one silent man, and no more. Three other limits are worth stating plainly: what the coin does about liars, how quick it is, and whether it reaches a good answer.
Nobody lies at the foot of the hill. For men who may lie as well as die there is a second arrangement of the same shape: each man must be able to tell whose bird they hold, and the liars must be fewer than one in five. Against one liar that is six men. The four bandits on the crown could not use it, and do not need to; they have their own methods.* Whether one in five is the best that can be done was not known.
With many men and many possible silences, the tosses that must all come up alike are many too, and the expected number of rounds may grow very fast. One happier case: if the silent are few, no more than about the square root of the number of men, and the birds happen to come in step, the rounds needed on average do not grow at all. No arrangement without coins can do that, since those need at least one more round than there are men who may fail.
The coins say nothing about which answer is wiser. When the sightings agree, the four do what they sighted; when they do not, the answer is whichever the coins and the birds happen to reach. As always on the hill, nothing follows from it: no assault is told, and no one learns whether it was the right answer.
Read the foot of the hill again with machines in the tents. Every tent is a process, every raven is a message, the arranger of the birds is the scheduler that orders the messages, and the coin is a random bit that each process draws for itself. Hover over a row, or tap it, to see who is who.
A machine that cannot decide may flip a coin: then no two machines ever decide differently, and every machine decides in the end with probability one.
The impossibility stands. The coin changes one of its hypotheses, and asks for a majority of machines that keep running.
Later work replaced the private coins with a shared coin, to make the expected number of rounds small.
Setting The Foot of Mount Phyle
Michael Ben-Or, Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols (extended abstract). Proceedings of the 2nd ACM Symposium on Principles of Distributed Computing (PODC), Montreal, August 1983, 27–30. The randomized consensus protocol for crash failures with N > 2t (Theorem 1), the Byzantine protocol with N > 5t (Theorem 2), and constant expected rounds when t = O(√N) (Theorem 3), stated without proofs.
The ideas. Fischer, Lynch and Paterson proved that no deterministic protocol can guarantee consensus in an asynchronous system if even one process may crash: an adversary ordering the messages can always keep the outcome undecided. Their proof depends on determinism, since the adversary must know in advance what each step will lead to.
Ben-Or showed that randomness removes the obstacle. Processes run in rounds. In each round every process broadcasts its current value, waits for N − t values, and broadcasts a proposal marked D if a strict majority of all N processes hold the same value. It then waits for N − t proposals: it decides on more than t D-proposals for a value, adopts the value on at least one, and otherwise flips a private fair coin.
Safety holds on every run. Two strict majorities intersect, so only one value can be proposed with D in a round; a decision means more than t D-proposals exist, so every process that finishes the round sees one and adopts the value, and all decide it in the next round. Termination holds with probability 1 when N > 2t: once every correct process holds the same value, the next round decides, and the coin flips keep giving that a chance the adversary cannot remove. Ben-Or states this without proof; a complete proof, which must handle an adversary that sees earlier flips, is Aguilera and Toueg's (2012). Runs that never terminate still exist, but together they have probability zero.
The protocol does not contradict FLP; it changes a hypothesis. It needs a correct majority, which is necessary, and it may take many rounds. Later work replaced the private coins with a shared coin to make the expected number of rounds small.