← The Books

Agreeing When Messages Run Late

If messages can run late without limit, agreement cannot be guaranteed; yet real networks are prompt most of the time. Can a protocol stay safe however late messages run, and still decide once they arrive on time again?

We find out by exploring how the same Greek mercenaries, on a windy night when no one could tell how long a raven would take, agreed whether to attack or hold once the wind had dropped.

After Cynthia Dwork, Nancy Lynch and Larry Stockmeyer, Consensus in the Presence of Partial Synchrony, 1988

On a moonlit night, with the wind bending the pines and cypresses, a mercenary in a blue cloak crouches at the mouth of a tent on a rocky headland above the sea, holding a sandglass up to the moon
Where this book sits
Draws on
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

Safe always, live once the network settles

A group of computers must all settle on the same one of two values, and any message between them may be late.

If messages may be late without limit, no protocol can promise that the machines ever decide, because a machine that has stopped cannot be told from one whose messages are slow. Real networks are prompt most of the time, though. So suppose the delays settle: until some unknown moment a message may take any time at all, and from then on every message arrives within a bound the machines know. One machine may also stop at any moment, without a word.

  • Agreement under partial synchrony (Dwork, Lynch and Stockmeyer, 1988): a protocol can be built that never lets two machines decide differently, however late messages run, and that has every sound machine decide once delays settle, though none can tell when they did.
  • More than half must stay sound. The protocol needs that, and no protocol manages with less.

The first result keeps safety apart from the network's behaviour, and only the deciding waits for the calm. We tell it with four mercenaries, their ravens, and a wind.

Is the network prompt yet?

MACHINE A
?
MACHINE B

A asks B for a reply and allows 2 seconds for it.

A lone linen tent with a shield and a chest on a rocky slope below a ring wall on the summit, cypresses and pines around it
The foot of Mount Phyle

Four tents, out of sight of one another

Four mercenaries camp at the foot of Mount Phyle, one to a tent, with the tents out of sight of one another, and they send word only by raven.* They must all attack the hill together, or all hold.

Only ravensA raven always arrives in the end, and it brings exactly what was written.
Nobody liesNo man at the foot of the hill ever misreports anything.
One may dieAny one of the four may be killed, and a dead man's tent falls silent and stays silent. Nobody is killed in this telling. What matters is that one may be.
What the four want

All attack, or all hold

The four must act as one, because an attack by fewer than four may meet more than it can handle, and a hold with a man missing leaves the hill open.

Each man formed an opinion at dusk from the quarter in view, a sighting: attack, or hold. The sightings may differ, so the four have to settle on one answer by raven. A man commits by leaving the tent: to strike it and go round the slope to climb with the others, or to lie by the path down a gully and hold. Committing is final, and what a man thinks before it does not count. The four ask three things of any arrangement they make.

First demand

No two commit differently

Nobody attacks while another holds.

Second demand

A shared sighting wins

If all four sighted the same answer, that is the answer they commit to.

Third demand

Every living man commits

Every man who is not killed eventually commits.

With no promise about the birds, the four cannot be sure of meeting all three, because no arrangement guarantees that anybody ever commits.* Two things together make the trouble: there is no longest flight, and a dead man's silence looks exactly like a slow bird. A longest flight would change that, since enough silence would then mean something.* No such promise is made at the foot of the hill.

Something less than a longest flight is enough, and it comes from the very thing that keeps the ravens late.

The only promise

The wind keeps the ravens in the folds

The thing that keeps a raven late is the wind. While it blows, a bird let go into the gullies goes down among the hill's crows and sits it out in the pines, for an hour or for the night, and nobody can say for how long. A bird that has gone down may stay there as long as it likes, even after the wind has dropped.

A bird let go in still air comes straight. The promise is that the wind always drops in the end, and once down it stays down. From then on no bird let go in still air takes longer than a short span that every man knows. That is the whole change from a night on which nothing can be arranged. Without it nobody could count on the wind dropping, and here the four can. Below, tent 1 lets a bird go to tent 2 in each span. Let the spans pass, and try to tell from the birds alone when the wind dropped.

Under a full moon, with the wind bending the pines and cypresses of the hill, a raven with a message tied to its leg sits among a flock of crows on a bare branch, waiting out the wind

Birds let go in the wind one span at a time

0birds let go0taken in within their own span

In each span, tent 1 lets a bird go to tent 2. Let the spans pass and watch which birds come in time.

The page draws the moment the wind drops at random and keeps it from you, as the hill keeps it from the men. The birds' delays are drawn by the rule above: any length in the wind, and a bird let go in still air within its span.

The four cannot see the wind drop, and the birds above did not show it either. A lull at one tent says nothing about the folds two spurs away, where a bird may still sit in a pine, and a lull that ends in a fresh gust looks exactly like the end of the wind. No man ever knows that the wind has dropped over the whole hill. Each knows only that it will, and without that, nothing could be arranged.*

So the four need an arrangement that never commits two men to different answers however long the wind blows, since no one can tell when it stops, and that has everyone commit once it has stopped. The promise speaks of a short span of time, and a man alone in a tent first needs a way to measure one.

A count every man shares

Glasses and late birds

Every man measures the span with sand. Each tent has a sandglass, and the four glasses run alike. When the last light left the top of the hill, seen from every tent at one moment, every man started the glass.

A man starts the glass again the moment it runs out, and counts the glasses. The four started together and run alike, so all four always have the same count. The glasses do drift over a night, as sand does, but by less than a flight, which is all that is needed. The last light is no signal, since no man made it. It is the only common moment the four have, the sun made it once at dusk, and nothing like it comes again until morning. The bandits cannot use it on the crown: their posts lie on different slopes, where the hill's shoulders take the light from each at a different moment, and the chief inside the wall sees only sky.

A glass is long enough for a man to write and tie a strip for every tent, and for any bird let go in still air to reach its perch before the sand runs out. That is what the known span buys: once the wind is down, a bird let go in a glass is taken in within the same glass. A bird that comes later than that is dealt with by rule.

Every strip

Carries its glass

A strip is written with the count of the glass in which it was written.

A late bird

Is read, and set aside

A strip taken in during a later glass than its own counts for nothing: not what it asks, not what it answers, not what it says was seen at dusk.

One exception

The parting bird

One kind of bird is taken in whenever it comes. It is met further on.

Birds come in at tent 2 below. For each one, compare the glass written on its strip with the glass in which it is taken in.

Birds at a tent pole taken in, or set aside

0counted0set aside

A bird comes in at tent 2. Is it taken in, or set aside?

The page draws each bird at random. What is done with it follows the rule above.

Setting birds aside loses nothing that matters, and it makes every glass stand alone. What a man does in a glass depends only on the birds written in that glass, and while the wind blows, a glass's birds may simply fail to come.

The glasses mean something only because the wind drops. Take that away, and what is left is a night on which nothing can be arranged.* With no longest flight, a glass that runs out with no bird tells a man nothing, however many glasses are counted. What gives the glasses their meaning is the wind's dropping, and no man sees that.

Every man now shares a count of glasses, and late birds are set aside. The four still need something to do with that count.

The hill, as this telling uses it, stated in the paper's terms

(1) While the wind blows, a bird may take any time. None is lost.
(2) The wind drops at some moment and stays down. From then on, a bird let go in a glass reaches its perch within the same glass. A bird let go before the drop may still be in the pines.
(3) No man knows when the wind has dropped.
(4) The glasses were turned together at last light and run alike, so every man's count of glasses is the same.
(5) Late birds: a strip taken in during a later glass than the one it was written in is set aside, except a parting bird.
(6) At most one of the four is killed. No one lies.

Communication is partially synchronous, “Δ holds eventually”: the bound Δ is known and holds from an unknown global stabilization time (GST) on, §2.3. Processors are synchronous, Φ = 1, §4. Each processor simulates a round of the basic round model in a group of N + Δ steps, and a message that arrives in a later round is ignored, §4.1. Fail-stop faults, N = 4, t = 1.

Who may propose

Turns and pledges

The four use the count to take turns. They group the glasses in fours, and each four is a turn. The first turn is glasses one to four, the second five to eight, and so on through the night.

A turn belongs to one man, in the order of the tents' numbers: the first to tent 1, the second to tent 2, the fifth to tent 1 again. That man is its owner. The owner is no leader. Nobody chose the owner. The count of glasses did, and it would have chosen a dead man just the same. The owner gives no orders, and may only put forward an answer that three men, the owner included, have already said they could accept. The turn passes when its fourth glass runs out, whatever has happened in it. Besides a sighting, each man keeps two things, and one word goes with them.

What each man keeps

The sighted answers

The answers the man knows someone sighted. The list starts as the man's own sighting, every strip carries it, and a man adds whatever a strip names. If all four sighted hold, only hold is ever on any list.

What each man keeps

Pledges

A strip tied to the tent pole, naming an answer and a turn: hold, turn five. It means that the owner of turn five may have committed to hold. A man may hold pledges on both answers at once.

A word for it

To accept

A man can accept an answer while holding no pledge on the other answer.

Each of a turn's four glasses has one task: asking, calling, answering, untying. Scroll slowly to watch turn five run in still air, and keep an eye on the pledges at each tent.

1 · The owner

Turn five is tent 1's

Still air: every bird comes within its glass. Tent 3 sighted attack and the others hold, and every man has heard that both answers were sighted. One pledge is left from an earlier turn: tent 2 holds attack, turn two, and nobody committed on it.

2 · The asking glass

Every man names what can be accepted

3 · The calling glass

The owner counts, and calls

4 · The answering glass

Pledges are tied, and the owner commits

5 · The untying glass

An older pledge is untied

The numbers in a turn come from the four and the one who may be dead. An owner can never count on hearing from more than three, and never waits for a fourth, so a call needs three men who can accept its answer. An owner commits on two pledged, and two is enough, because two pledges on an answer leave only two men who could accept the other, and the other would need three.

Nobody decides which answer is better. Which answer the four commit to is settled nowhere here, and an owner who may call either answer calls either. The arrangement is indifferent to which.

The sighted answers are there to keep the second demand. An owner calls only an answer that three men named from the answers they know were sighted, and an answer enters that list only because someone sighted it. If all four sighted hold, attack is on nobody's list, and nothing but hold can ever be called.

Turn five ran in still air. In the wind, birds come late, are set aside, or sit in the pines for glass after glass, and pledges tied on such a night must still never commit two men to different answers.

The four glasses of a turn, stated in the paper's terms

The asking glass. Every man, the owner included, sends the owner the answers that man can accept and that are among the sighted answers.
The calling glass. If at least three men, the owner included, named the same answer, the owner calls it, sending pledge to hold, turn five, say, to every tent, the owner's own included. If both answers qualify the owner calls either; if neither, the owner calls nothing.
The answering glass. A man who took in the call in the calling glass ties a pledge for that answer and turn, unties any earlier pledge on the same answer, and sends the owner pledged. A pledge on the other answer stays where it is. If the owner takes in pledged from at least two men, the owner possibly among them, the owner commits to the answer called.
The untying glass. Every man sends every tent all the pledges tied there, answer and turn. A man with a pledge on one answer who learns of a pledge on the other answer at a turn as late as that pledge's own, or later, unties it.

Algorithm 1, §3.2.1: trying phase k of three rounds and lock-release phase k of one; phase k belongs to pi when k ≡ i (mod N). A proposal needs N − t = 3 processors finding the value acceptable and proper; a decision needs acknowledgments from t + 1 = 2. The sighted answers are the PROPER set.

Safety asks nothing of the wind

Never two answers, in any wind

Pledges tied in the wind are safe only if the first demand, that no two commit differently, holds in any wind. It has to, because nobody can tell when the wind drops. If it held only in still air, the four would never know whether it did. So the arrangement is built so that the first demand needs nothing from the wind at all.

Two facts carry it. The first is small: in any turn only the owner calls, and at most one answer, so no two men tie pledges on different answers for the same turn. The second is the heart of it. Take the earliest turn in which anyone committed, say to hold in turn five. The owner had pledged from two men, so two men tied hold, turn five. To lose that pledge, one of them would have to untie it on hearing of a pledge to attack in a turn as late as five. By the first fact there was none in turn five, so it would be a later turn, say turn eight. But for attack to be called in turn eight, three men had to be able to accept attack in its asking glass, which means three men with no pledge to hold. Two of the four still had one, and that leaves only two.

Never Two Answers

However long the wind blows and however the birds are delayed, no two men ever commit to different answers. If all four sighted the same answer, no man commits to the other.

The counting can be tried below. Choose how many men tie the pledge to hold in turn five and how many of their pledged birds come in time, and see whether attack can still be called in a later turn.

Pledges in turn five, and a call to attack later try each count

Men who tie hold, turn five
Pledged birds in time

Which men tied the pledge does not matter, only how many. The page counts by the rules of the turn: an owner commits on at least two pledged, and a call needs three men who can accept.

The wind comes into this nowhere. The argument uses only the counting: two pledges that cannot be untied, and three men needed to accept the other answer, among four. Birds may arrive late, be set aside, or not come at all in the glass they were meant for. Each of those only makes a call or a pledged fail to happen, and failing to happen is always safe. That is why the arrangement can run straight through the wind without anyone knowing when it ends.

Untying has a reason of its own. A pledge from a turn in which nobody committed, because the owner's pledged birds were in the pines, would otherwise sit on its tent pole all night and forbid its tent to accept the other answer for ever. The untying glass lets a later call, which knew more, override it. What it can never override is a pledge held by the two men of a turn in which someone committed, because no later call against that answer can gather three.

Nobody commits to a wrong answer, in any wind. An arrangement in which nobody ever commits would manage that too. The third demand asks for more: once the wind has dropped, every living man must commit.

Proof · that no two men commit to different answers, in any wind

In the paper's terms a turn is a phase, a pledge is a lock, to accept an answer is to find a value acceptable, and to commit is to decide; k and h are turn numbers, N = 4 and t = 1. Theorem 3.1 and Theorem 4.1(a). However messages are delayed, no two processors decide different values (consistency), and if all four started with the same value no processor decides another (strong unanimity).

  1. One answer per turn. Only a turn's owner calls, and the owner calls at most one answer in it. A pledge for turn k is tied only on taking in the call of turn k. So all pledges for turn k are on one answer.
  2. Suppose some man commits, and let turn k be the earliest turn in which an owner committed; say that owner committed to hold. The owner had pledged from two men, so two men tied hold, turn k. Men who commit on a parting bird (described below) commit to an answer some owner committed to earlier, so it is enough to show that no owner in a later turn commits to attack.
  3. The two keep a pledge to hold. Suppose not, and take the first untying glass in which one of the two unties a pledge to hold for turn k or later without having a later one. That man unties it on learning of a pledge to attack for some turn h at least as late. By step 1, h is not k, so h is later than k, and no later than this untying glass.
  4. A pledge to attack for turn h means attack was called in turn h, so three men could accept attack in turn h's asking glass: three men with no pledge to hold. But both of the two had a pledge to hold from turn k until this untying glass, which is no earlier than turn h's own. There are four men; at most two had no pledge to hold. This contradicts the three.
  5. So from turn k on, two men always have a pledge to hold, or have committed to hold and send nothing. In no later asking glass can three men name attack, attack is never called, no man ties a pledge to attack for a later turn, and no owner commits to attack.
  6. The second demand. An answer is named in an asking glass only if it is among the sighted answers, and an answer enters that list only through someone's sighting. If all four sighted hold, only hold can be named, called or committed to.∎
The third demand

Committing once the wind drops

The third demand turns first on what happens when one man commits. Committing is silence: a man who has left the tent has left its birds, and sends no more and ties no more pledges. So a man who commits first says so, by sending each other tent a parting bird: parting, hold.

A parting bird carries no turn and is never set aside. A man who takes one in, at any glass, sends parting birds of their own to every tent and then commits to the answer it names. Every man who commits sends a set, and not only the first, because a man may be killed halfway through tying them, with two sent and one not. Whoever received one sends a full set. Since at most one man is killed and no bird is ever lost, the birds of the others reach every tent in the end, and every man left alive commits. This is the paper's own device: a man who decides there tells everyone, anyone told decides at once, and where nothing is ever lost a man who has told may stop. So once one man commits, the third demand is settled, and what remains is to show that some man commits once the wind has dropped.

In still air a turn owned by a live man ends with someone committing, as turn five did. While the wind blows, a turn can fail in three places.

First place

The asking birds are in the pines

The owner hears from two men and calls nothing.

Second place

The call is late

The owner calls, and the call reaches one man in time.

Third place

The pledged birds are late

Three men pledge, and their pledged birds come in the next glass and are set aside.

Each failure leaves pledges tied that nobody committed on. An untying glass run in still air clears them: every man then hears every live man's pledges within the glass, and any pledge on one answer that is no later than some pledge on the other is untied. What is left is on one answer at most.

Then take the next turn owned by a live man. In its asking glass every live man hears from every other, and at least three are alive. The sighted answers have gone round, so every list is the same, and all the pledges still tied are on one answer, which every live man can therefore accept. So the live men all name a common answer, the owner calls it, every live man pledges, and the owner has two pledged before the answering glass runs out.

Committing After the Wind

If the wind drops, every man who is not killed commits. If nobody had committed when it dropped, all commit within twenty glasses of the drop. If someone had, they commit when that man's parting birds arrive, which is certain but bounded by no count of glasses.

The count of glasses can be followed below. Choose the turn and the glass in which the wind drops, and see which turn the count relies on and how many glasses pass before its owner commits.

When the wind drops choose the turn and the glass

The wind drops in turn
in that turn's glass
the wind dropswholly still glasscommits, every man alivecommits, if the owner of the first turn is the silent one

Choose when the wind drops. The men cannot see it. Only the page knows.

The page counts glasses as the proof does and does not run the pledges. It shows two possible nights: one in which every man lives, and one in which the owner of the first turn it would use is the silent one. Nobody is killed in either; the second is only the night the count must also survive.

Twenty is the paper's number: four glasses to a turn, and five turns after the wind drops. The proof below is a little tighter, but nothing depends on it. The paper's men earn their bound by never stopping, since a man who has decided there goes on taking part. On the hill a man who commits has left the tent. If one commits while the wind blows and another is dead, the two left cannot gather three names for a call, and they wait for the parting birds, which will come, but at no glass anyone can count.

Nor can anyone say, at some glass of the night, by now we will have committed. The bound counts glasses after an event no man sees, so nobody knows from which glass to count.

The arrangement bears one death among four. Whether a cleverer one could bear two is the next thing to settle.

Where the allegory leaks

A night ends. The paper's rounds do not: it lets the wind blow for as long as it likes before dropping, and then promises a decision within a fixed number of rounds after. On the hill, if the wind drops late, dawn may come first. The model has no dawn, and nothing here turns on one: the first demand holds at every glass of the night, and the third is a promise about glasses after the drop, however many there are.

Proof · that the four commit once the wind has dropped

In the paper's terms the wind drops at the global stabilization time GST, and a glass is a round. Termination (Theorem 3.1; Theorem 4.1; §3.2.1). Every correct processor decides by round GST + 4(N + 1), with N = 4 and t = 1. If some processor had already decided when the wind dropped, the others decide when its “decide” arrives. h is a turn number.

  1. From the glass after the wind drops, every bird let go by a live man is taken in within its own glass, so no bird between live men is set aside.
  2. After a still untying glass, pledges are on one answer at most. In it every live man hears all the pledges of every live man. If live men have pledges on both answers, take the latest turn among them, say turn h on hold; by the first step of Never Two Answers there is no pledge to attack for turn h. Every pledge to attack is for a turn no later than h, and the man at its tent, hearing of hold, turn h, unties it.
  3. Every man knows the same sighted answers. Every strip carries its sender's list, and in a still untying glass every live man hears from every other. After it, an answer that any live man knows was seen is known to all of them. An answer still pledged was called by some owner, who called it from a list, so it is among them.
  4. If some man had already committed when the wind dropped, that man's parting birds are never lost, so they reach every tent in the end and every man left alive commits. A parting bird let go while the wind blew may still be in the pines, so no count of glasses bounds this. So suppose no one had committed when the wind dropped. From then on a man who commits sends parting birds in still air, and they arrive within the glass.
  5. The wind drops during some turn. The untying glass of the turn after it is wholly still. Of the two turns after that, at least one is owned by a live man, since only one man may be dead. Take the first of them owned by a live man: it begins within three turns of the drop and ends within four, sixteen glasses.
  6. In its asking glass, each of the live men, at least three, names every answer on the common list that the man can accept. If some answer is still pledged, every live man can accept it, since no pledge on the other answer remains; and it is on the list. If none is pledged, every live man can accept every answer on the list. Either way at least three men name a common answer, and the owner hears them all within the glass and calls it.
  7. Every live man takes in the call within the calling glass, pledges and sends pledged; the owner takes in at least two within the answering glass and commits, sending parting birds, within sixteen glasses of the wind's dropping.
  8. By the parting birds, every man left alive then commits, and by Never Two Answers they all commit to the same answer.∎
What the arrangement cannot bear

Two against two

Two deaths among four are more than any arrangement could bear, however clever. The reason is the wind again, now working against the four.

Suppose any two of the four might be killed. A pair that has heard nothing from the other pair cannot wait for it, because the other two may be dead, and the third demand says the living must commit. But the other two may just as well be alive, with every bird between the pairs in the pines, and the wind will drop only after the living pair has committed. Three nights side by side show what follows. In the first two, one pair is silent from dusk. In the third nobody is, and the wind does the rest. Let some glasses pass, and say when each pair gives up waiting.

Three nights give up waiting, pair by pair

Let some glasses pass, then say when tents 1 and 2 give up waiting for tents 3 and 4.

You choose the glass at which each pair gives up, since the arrangement may take any number of glasses. Nothing else is chosen: the pair's answer in each of the first two nights is forced by the three demands, and the wind in the third night is held for as long as it needs to be.

More Than Half

If two of the four may be killed, no arrangement meets the three demands, even with glasses, even if the wind always drops, and even if all that is asked of the second demand is that four live men who sighted the same answer commit to it.

The wind split the four. In the third night nobody is dead, yet each pair's night is the same as one in which the other pair was dead, so each pair commits alone and the two commit to different answers. The argument did not need the number four, only two sides, each small enough to be dead. Any number of men of whom half or more may die can be split in the same way. So the arrangement's ratio is the right one: it bears some number of deaths among men when there are more than twice as many men as may die, and no arrangement bears more.

The argument is the camps' own. A dead man looks exactly like a slow bird,* and here the likeness is used once, for a fixed length of time, rather than for ever. That is the difference the wind's dropping makes. It cannot make silence mean death, but it limits how long the confusion can last, and an arrangement that waits for more than half can outlast it.

The mercenaries may die, and they never lie. On the crown the same wind blows over men who may lie, and there it costs more.

Proof · that four men cannot bear two deaths

In the paper's terms this is Theorem 4.3: there is no t-resilient consensus protocol for fail-stop faults when N ≤ 2t, even for weak unanimity and binary values. Here N = 4 and t = 2. A and B are numbers of glasses.

  1. Suppose some arrangement does. Divide the four into two pairs, tents 1 and 2 on one side, tents 3 and 4 on the other.
  2. The first night. All four sighted hold. The men of tents 3 and 4 are dead from dusk, and every bird between tents 1 and 2 is taken in within its glass. Two deaths are allowed, so by the third demand the men of tents 1 and 2 commit, within some number of glasses, say A. They commit to hold. For if they committed to attack, take a night the same for them in every respect, except that the men of tents 3 and 4 are alive and sighted hold, and the wind holds every bird from them for more than A glasses before dropping. Tents 1 and 2 cannot tell that night from this one, so they commit to attack, though all four were alive and sighted hold.
  3. The second night. All four sighted attack; the men of tents 1 and 2 are dead from dusk; by the same argument tents 3 and 4 commit to attack within some B glasses.
  4. The third night. Tents 1 and 2 sighted hold, tents 3 and 4 attack. Nobody dies. Birds within each pair are taken in within their glass, and the wind holds every bird between the pairs for more than A and more than B glasses, and then drops. That is a night the wind allows.
  5. Tents 1 and 2 cannot tell the third night from the first until more than A glasses have passed, and by then they have committed to hold. Tents 3 and 4 cannot tell it from the second, and have committed to attack. Two men committed to different answers, which contradicts the first demand.∎
The same wind, on the crown

Liars and seals

The men who may lie are the bandits on the crown. Some of them do,* and on the later nights of the siege the same wind blows there, holding the rats in their holes between the posts for as long as it lasts.

On the crown's first night there was no wind, and the runs were short. There, with sealed orders that no one can forge, the chief's word can be carried to any number of posts with any number of liars among them.* That does not survive the wind. The paper answers for liars too, and its answer belongs to the crown, not to the camps. It is set down here because it is the same wind. Choose the wind, the trouble that may befall the men, and how many it may touch, and the table gives the number of men needed.

How many men are enough? choose the wind and the trouble

The wind
Men who may
How many may

The answers are the paper's table, applied by the page: more than twice as many men as may die or drop birds, and more than three times as many as may lie.

The middle choice, a wind that drops, is the hill's own case: glasses that run alike and a wind that drops in the end. There, seals change nothing. Four posts bear one liar, sealed or not, and three posts bear none.

Seals stop helping because of the wind again. On the crown's first night a post that heard nothing within the round knew that nothing was sent, and could read the silence itself. Under the wind a man can never wait for everyone, since one may be a man whose birds are in the pines and another a liar keeping quiet. Waiting is possible only for all but the few who may fail, and among the ones heard from, some may be liars answering promptly. A seal stops a liar forging another man's word. It does not stop a liar answering promptly while an honest man's bird is still in a pine, and from the liar's own mouth two men may be told two different things.

The crown has four men and bears one liar. On a windy night those four keep a loot scroll together, with seals and a chief's job that passes from man to man.* That is the crown's matter. The wind and this table belong to both.

A wind that drops is enough, then, with more than half alive. Some things it has not given the four, and they are set down last.

The paper's table of liars and seals

This is Table I of the paper: the smallest N for a t-resilient protocol. The middle column is its third, the one for partially synchronous communication and synchronous processors.

Who may fail, and howNo windWind that dropsWind for ever
men who may dieany numbermore than twice as many as may die: 2t + 1no arrangement
men who may drop birds, or fail to take them inany number2t + 1no arrangement
men who may lie, with seals no one can forgeany numbermore than three times as many as may lie: 3t + 1no arrangement
men who may lie, without seals3t + 13t + 1no arrangement
Proof · sealed or not, three posts cannot bear one liar under a wind that drops

In the paper's terms this is Theorem 4.4: there is no t-resilient consensus protocol for authenticated Byzantine faults when N ≤ 3t. Here N = 3 and t = 1; P, Q and R are the three posts.

  1. Take three posts, P, Q and R, of whom one may lie, and suppose some arrangement meets the three demands.
  2. The first night. All sighted hold. R is silent from dusk, which a liar may be. P and Q must act without R, within some number of glasses, and, as with the two pairs of men, they must choose hold.
  3. The second night. All sighted scatter. P is silent from dusk. Q and R choose scatter, within some number of glasses.
  4. The third night. P sighted hold, R scatter, and Q is the liar. To P the liar behaves exactly as on the first night, to R exactly as on the second, sealing every strip honestly with the liar's own seal. The wind holds every bird between P and R until both have acted. P cannot tell this night from the first, nor R from the second, so they choose differently.∎
Questions left over

What the wind does not say

What the wind has not given the four all comes from one thing. The wind is a fact about the hill, and the arrangement uses it without ever seeing it. Eight things follow from that.

Does anyone learn when the wind dropped?

Nothing in the arrangement detects the calm, so no man ever learns of it. The four run the same turns in the wind and after it, and the proofs do the knowing on their behalf. A man who commits knows only that two pledged birds came in time, and a man still waiting cannot tell whether the wind is still up or the owner is dead.

Would the glasses alone have been enough?

Glasses started together, with no longest flight, leave the four able to arrange nothing.* A glass that runs out with nothing at the perch tells a man only that a glass has run out. What makes the glasses count is the promise about the wind. Take either away, the common count or the dropping wind, and nothing can be arranged.

What if the glasses had not been started together?

The four here have one common moment, the last light on the crown. The paper also answers for men with none, whose glasses run at somewhat different rates. They make a common count by birds alone: each sends the others the count reached, and moves on only when enough others show they have passed it, never so far that the dead or the slow could not catch up. This is a clock kept by ravens. It needs the same more-than-half, and its proof is long.

What if nobody knew how long a still flight takes?

Here every man knows the span of a still flight, and a glass is made to fit it. The paper also answers for men who know only that some such span exists. Each glass is given a little more time than the one before, so that in the end the glasses outlast any flight, and from then on the arrangement works as before.

Is there a bound before the wind drops?

There is none. The twenty glasses are counted from a moment nobody sees, and how long the wind blows is up to the wind. On a night when it never drops, nobody can be made to commit.* Nobody commits to a wrong answer either.

Does it matter that no bird is lost?

It matters for stopping. The four can leave their tents and commit because a parting bird, once let go, always arrives. If birds could be lost while the wind blew, the paper observes that some man would have to go on sending for ever, however the arrangement was made, since no one could be sure a parting bird had reached the others.

Is the wind the only way out?

There are other ways out at these tents, each changing one thing. Men who may each toss a coin, alone in a tent, commit with probability one, on no night anyone can name.* Men each given a slate that in the end chalks the dead, and in the end spares one living man, can agree while a majority is alive.* Here nothing is given to the men, and the change is in the wind. The three differ in kind: the coin needs no promise about time and gives none, the slate is granted and not built, and the wind is a fact about the hill. The turn that passes round the tents in number order, fixed by the count and not by anyone's command, is also how men with such slates take turns to propose.*

What follows from committing?

Nothing follows. The four attack together or hold together. What happens then is not the subject of this telling or any other: no assault is made, no wall is carried, and nobody surrenders.

Back to machines

The camp was a group of machines

Read the foot of the hill again with machines in the tents. Every tent is a processor, every raven is a message, and the wind is a network whose delays settle at a moment no machine sees. Hover over a row, or tap it, to see who is who.

At the foot of the hill
In the machine room

When messages may be late for as long as they like but are prompt from some moment on, a protocol can be safe in every case and still decide once the delays settle.

Agreement is never broken, in any wind. What the settled network adds is an end to the waiting, though no machine can tell when it came.

The Foot of Mount Phyle, in detail All the papers

Setting The Foot of Mount Phyle

At the camps and in the paper: the whole table

So that the reader may check the windy nights at the camps against the paper of Dwork, Lynch and Stockmeyer.

At the campsWhat it means
the four mercenariesThe processors, N = 4. §2.1.
a sighting, attack or holdA processor's initial value, from a binary domain. The protocols work for any domain V; the lower bounds hold already for |V| = 2. Technical Remark 3.
committingAn irrevocable decision. §2.1.
the three demandsConsistency; strong unanimity; termination. §2.4.
a man who may be killed; at most oneA fail-stop fault; t = 1. §2.2.
ravens, never lostMessages that are delayed but not lost. The strengthened model of §4.2, Remark 2.
the wind; its dropping; a still flight within a glassUnbounded delay before an unknown time, and a known bound after it. “Δ holds eventually”; GST; §2.3.
no man knows when the wind droppedGST is unknown to the processors. §1.2.
glasses started together at last light, run alike; the countCompletely synchronous processors with a common step count. Φ = 1, §4.
a glassA round of the basic round model, simulated by N + Δ steps. §3.1, §4.1.
a late bird, set asideA message arriving in a later round than it was sent is ignored, so rounds are independent. §4.1.
a turn; its owner, in number orderA trying phase of three rounds and a lock-release phase of one; phase k belongs to pi when k ≡ i mod N. Algorithm 1, §3.2.1. The same rotation as the coordinator of Chandra and Toueg's ◇S algorithm.
the sighted answersThe set of values a processor knows to be proper, piggybacked on every message. PROPER, §3.2.
a pledge on the tent pole; accepting an answerA lock with its phase number; a value is acceptable if the processor holds no lock on another value. §3.2.1.
the asking glassEach processor sends the phase's owner its acceptable, proper values. Round s = 4k − 3.
the calling glassThe owner proposes a value that N − t processors found acceptable and proper: (lock v, k). Round s + 1.
the answering glass; committing on two pledgedReceivers lock v, releasing only earlier locks on v, and acknowledge; the owner decides on t + 1 acknowledgments. Round s + 2.
the untying glassAll locks are broadcast; a lock on v at phase h is released on learning of a lock on w ≠ v at phase h′ ≥ h. Lock-release phase, round 4k.
one answer per turnLemma 3.1.
the two keep a pledge on the answerAfter the first decision, at least t + 1 processors keep a lock on its value at that phase or later. Lemma 3.2.
Never Two AnswersConsistency and strong unanimity hold however messages are delayed. Theorem 3.1; Theorem 4.1(a).
after a still untying glass, one answer at mostLemma 3.3.
Committing After the Wind; twenty glassesTermination; all correct processors decide by round GST + 4(N + 1). Theorem 3.1; §3.2.1; time bound 4(N + 1)(N + Δ) after GST in Theorem 4.1. The paper's processors keep participating after deciding; with halting (Remark 2), a decision made before GST gives termination without that bound.
a parting bird, sent by every man who commits“Decide v”, untagged, accepted at any time; a receiver decides at once; with fail-stop faults a processor may halt after sending it. Remarks 1 and 2 (§3, §4.2). Each send is a separate step: there is no atomic broadcast, Technical Remark 1.
More Than Half; the three nightsNo t-resilient consensus for fail-stop faults when N ≤ 2t, even for weak unanimity and binary values. Theorem 4.3, Scenarios A, B, C.
the table of liars and sealsThe smallest N for a t-resilient protocol. Table I; the middle column is its third, the one for partially synchronous communication and synchronous processors.
men who may drop birds, or fail to take them inOmission faults. §2.2; Algorithm 1 also covers them.
liars; sealsByzantine faults; authentication. §2.2; Algorithms 2 and 3.
three posts cannot bear one liarNo t-resilient consensus for authenticated Byzantine faults when N ≤ 3t. Theorem 4.4.
a clock kept by ravensDistributed clocks for partially synchronous processors. §5; for fail-stop faults the authenticated clock of §5.2, simplified, with N ≥ 2t + 1.
rounds given more time each time“Δ unknown”: round r is simulated by N + r steps. §4.2, Theorem 4.2.
some man sending for everIf messages can be lost before GST, some correct processor cannot halt. §2.4; Remark 2.
The paper behind this book

The paper behind this book. Cynthia Dwork, Nancy Lynch and Larry Stockmeyer, Consensus in the Presence of Partial Synchrony. Journal of the ACM 35, 2 (April 1988), 288–323. The two models of partially synchronous communication, the basic round model and Algorithms 1–3, the lower bounds (Theorems 4.3 and 4.4), and the distributed clocks for partially synchronous processors.

The ideas. Fischer, Lynch and Paterson showed that consensus is impossible in an asynchronous system if even one process may crash, because a crashed process cannot be told from a slow one. Dwork, Lynch and Stockmeyer asked how much synchrony is enough. Their answer is partial synchrony: either a bound on message delay exists but is unknown, or it is known but holds only from some unknown global stabilization time (GST) on.

In both models consensus is possible, and they determine exactly how many faults can be tolerated: with crash or omission faults, more than half the processes must be correct (N ≥ 2t + 1); with Byzantine faults, more than two thirds (N ≥ 3t + 1), whether or not messages are signed. The lower bounds are partition arguments: if half may fail, the network can delay every message between two halves until each has decided alone.

The protocols run in rounds grouped into phases, each phase belonging to one process in rotation. A phase's owner proposes a value that enough processes find acceptable; processes lock it and acknowledge; the owner decides on enough acknowledgments; a lock-release round lets a later lock override an earlier one. Safety holds under any delay, because the processes that locked a decided value can never all be outvoted. Termination follows once delays are bounded, because the first phase owned by a correct process after stabilization succeeds.

The separation between safety in all conditions and progress in good conditions, and rotating phases with locks carried forward, became the shape of later consensus protocols.

Dwork, C., Lynch, N., and Stockmeyer, L. Consensus in the presence of partial synchrony. J. ACM 35, 2 (1988), 288–323.