A machine that has crashed looks exactly like one that is merely slow, and that alone makes agreement impossible. How well must we tell the dead from the slow before agreement becomes possible again?
We find out by exploring how the same Greek mercenaries, each keeping a slate of the tents he thought dead, agreed whether to attack or hold though the slates were often wrong.
After Tushar Deepak Chandra and Sam Toueg, Unreliable Failure Detectors for Reliable Distributed Systems, 1996
The Weakest Failure Detector for Solving ConsensusChandra, Hadzilacos & Toueg 1996
failure detector classesFailure detector classes, and the weakest one that still allows consensus.
Failure Detection and Consensus in the Crash-Recovery ModelAguilera, Chen & Toueg 2000
failure detectorsFailure detectors, extended to processes that crash and recover.
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
A guess about who has crashed
A machine that has crashed looks exactly like one that is merely slow, and that alone makes agreement impossible: a machine waiting on a silent one cannot know whether to go on waiting.
A failure detector is a module on each machine that lists the machines it suspects have crashed. The list may be wrong, often. Two properties are asked of it: crashed machines are eventually suspected, and live ones are not. Chandra and Toueg (1996) found how little of the second is enough.
One correct machine never suspected: agreement survives any number of crashes.
The same, but only eventually: agreement survives while more than half the machines live.
The detector is never told how to guess. It is judged only by what its lists get right. We tell it with four mercenaries, their ravens, and a slate at each tent.
Crashed, or only slow?
MACHINE A
?
MACHINE B
A has asked B for its value and is waiting for the reply. A's failure detector lists the machines A suspects.
The foot of Mount Phyle
Four tents, out of sight of one another
Four mercenaries are camped at the foot of Mount Phyle, one to a tent and under nobody's command, and no tent can be seen from another.* Bandits hold the top of the hill.
Only ravensThe four send word to one another only by raven. A bird always arrives, but no bird has a longest flight.
Nobody liesNo man at the foot ever misreports anything, so whatever a bird carries is true.
Any man may dieAny of the four may be killed in the night. A dead man's tent simply falls silent, and no bird reports the death.
Three demands, one change
A slate at every tent
The four must all attack or all hold. Each formed an opinion at dusk, a sighting, and the sightings may differ. Committing to either answer takes a man from the tent and its birds for the night, so a man who has committed sends and hears nothing more.
Whatever arrangement the four follow to settle on one answer, three things are demanded of it.
First demand
No two commit differently
No two of the four commit to different answers. Nobody attacks while another holds.
Second demand
Only a sighted answer
A man commits only to an answer that one of the four sighted at dusk.
Third demand
Every living man commits
Every man who is not killed commits in the end. Nobody is left waiting for ever.
The first two are easy to keep by never committing, and the third forbids that. On such a night no arrangement can be sure of meeting all three, because none guarantees that anyone commits. The trouble is a silent tent. A man waiting on one cannot tell whether the man there is dead or the bird is still in the pines.*
Both choices can go wrong. If the man waits, the wait may be for ever, on a dead man. If the man stops waiting, a live man whose bird was about to arrive may be left out.
Suppose each man had some help in telling the dead from the slow. That is the one change in this book. Each tent has a slate, with a row for every other tent. A man chalks a tent thought dead, and rubs the mark out when thinking again. A man with a slate knows when to stop waiting: when the silent tent is chalked. How a man decides to chalk is not the question here.
The slate is often wrong. A mark may stand against a live man whose bird is merely slow, and a dead man's row may stay clean for a while. So the four have to find out how good a slate must be before they can agree, and before that, what it means for a slate to be good at all.
Two ways to go wrong
How a slate may be wrong
A slate is good when it keeps clear of its mistakes, and it can make only two. It can fail to chalk the dead, or it can chalk the living. So two things are asked of it.
Keep a slate yourself for one night. You sit at tent 1, and some tents have sent no bird. Chalk the ones you think are dead, then reveal the night and see which of the two mistakes you made.
Mark a slate you are at tent 1
The dead
Chalking the dead
Every man who is killed is, in the end, chalked for good. This can be asked of every living man's slate, or only of some living man's.
The living
Sparing the living
A man who lives is not chalked. This can be asked in four strengths, of all the living or of one, from dusk or only in the end.
A warning
Chalking the dead is worth nothing alone
The warning is easy to check. A slate that chalks every tent all night chalks every dead man, and tells nobody anything, since a man who trusted it would wait for no one. It is the sparing of the living that makes a slate useful.
Sparing the living can be asked strictly or loosely, and how strictly it is asked decides what kind of slate a man holds.
Four strengths of sparing
Eight kinds of slate
Sparing the living is asked in four strengths, set out here from the strictest to the loosest. With the two ways of chalking the dead, by every living man or by some, they make eight kinds of slate.
Never chalked. No man is chalked while living.
One never chalked. Some man who lives through the night is never chalked by anyone.
In the end, never chalked. There comes a time after which no living man is chalked.
In the end, one never chalked. There comes a time after which some man who lives through the night is chalked by no one.
every living man chalks the dead
some living man chalks the dead
never chalked
perfect
-
one never chalked
strong
weak
in the end, never chalked
in the end perfect
-
in the end, one never chalked
in the end strong
in the end weak
Six of the eight have names in the table, and the other two will not be needed. The last row promises the least a slate can promise and still promise anything. Every living man may be chalked at one time or another, over and over, by everyone. All that is asked is that, from some moment nobody can see, one man who lives is left alone. No man knows when that moment has come, or who that man is.
Eight kinds of slate are a great many to study. The four need not study them all, because the two columns of the table come to the same thing.
The eight kinds, in the paper's names
Completeness, strong and weak; accuracy, strong, weak, eventual strong and eventual weak (§2.3). The failure detector classes of Fig. 1.
never suspected
one never suspected
eventually never suspected
eventually one never suspected
strong completeness
P
S
◇P
◇S
weak completeness
Q
W
◇Q
◇W
The two columns are one
Copying marks
The two columns come to the same thing because a mark can be passed on. If only some living man chalks the dead, the rest can be brought to chalk them too, by copying one another's marks.
Every man keeps a second slate, a copy. Again and again the man sends every tent the marks on the first slate. When a bird comes from a tent, the man adds its marks to the copy, and rubs out the mark against the tent the bird came from, since that tent was alive to send it.
In the rounds below tent 4 is dead, and of the three living men only tent 1 has chalked it. Early on, two slates also chalk a living man by mistake. Send the birds, and watch the mark against tent 4 reach every copy while the mistaken marks come and go.
Rounds of birds tent 4 is dead
If some living man in the end chalks every dead man for good, then with copying every living man does. That man goes on sending the mark, and no bird ever comes from the dead to rub it out. And the copy spares the living exactly as well as the slate it was copied from. A man whom no slate chalks is on nobody's list of marks, so no copy chalks that man. A man whom the slates stop chalking goes on sending birds, and each bird rubs that man out of a copy.
So only the first column matters: perfect, strong, in the end perfect, and in the end strong. Of these, two need study, strong and in the end strong. A perfect slate is also strong, and one in the end perfect is also in the end strong, so whatever works with the weaker works with the stronger.
Start with the stronger of the two. With a strong slate one living man is never chalked by anyone, and nobody knows which man that is. What has to be settled is whether so little is enough to agree.
Proof · that copying makes every living man chalk the dead, and spares the living as before
The reduction TD→D′ of Fig. 3, §3: every process p keeps outputp, repeatedly sends its own suspect list to all, and on receiving the list of q sets outputp to (outputp ∪ the list of q) − {q}. Theorem 1. If the detector D has weak completeness, output has strong completeness, and it satisfies the same accuracy property as D.
The dead. A dead man sends no more birds, so after the last of those birds arrives nobody rubs the dead man out. The living man who in the end chalks the dead man for good goes on sending those marks, and every living man adds them to a copy. So in the end every living man's copy chalks the dead man for good.
Never chalked, or one never chalked. A man that nobody's slate has chalked is on
nobody's list of marks, so nobody copies a mark against that man.
In the end. Suppose from some time no living man's slate chalks a certain living man.
The dead stop sending, so in the end no bird carries a mark against that man. That man goes on sending, and each such bird rubs its sender out of every copy. So in the end no copy chalks that man.∎
However many die
One man never chalked
One living man whom nobody ever chalks is enough. Suppose the slates are strong: every living man in the end chalks the dead, and one man who lives, say the man at tent 2, is never chalked by anyone. Nobody knows it is tent 2. The four can then agree however many of them die, even three.
Each man keeps a sheet of sightings: a row for each tent, holding that tent's sighting if the man has learned it, and blank if not. At first it holds only the man's own. The arrangement works in three parts to make every sheet come out the same, so that every man reads the same answer from it.
Spreading, three rounds
Send what is new
In each round a man sends every tent the sightings learned for the first time in the round before (in the first round, the man's own). The man waits for that round's bird from every tent except a tent chalked, and stops waiting for a tent chalked during the wait. Any new sightings go into the sheet.
Comparing
Send the whole sheet
The man sends every tent the whole sheet, and waits in the same way. Any row that is blank in any sheet received is blanked in the man's own.
Committing
First filled row
The man commits to the answer in the first row of the sheet that is not blank, taking the rows in number order.
Scroll to watch one night run. Tent 4 is killed in the first round, and the slates chalk living men by mistake. Follow tent 4's sighting, which reaches one sheet and no further.
1 · At dusk
Each sheet holds one row
Each man's sheet holds the man's own sighting, A for attack or H for hold. The man at tent 2 will never be chalked, though nobody knows it. Tent 4 is about to be killed.
2 · Round one
A bird reaches only one tent
Tent 4's bird reaches only tent 3 before tent 4 is killed. Tent 1 chalks tent 3 and does not wait for its bird, and tent 3 chalks tent 1. Tent 3's sheet now holds tent 4's sighting.
3 · Round two
Chalk hides a sighting
Tents 1 and 2 chalk tent 3 and do not wait for its bird. So tent 4's sighting, which only tent 3 holds, goes no further. Tent 3 waits for everyone, and learns tent 1's sighting.
4 · Round three
Nobody is chalked
Every bird is taken in, and nothing more is new. Tents 1 and 2 hold rows 1 to 3. Tent 3 alone holds a fourth row, which tent 2 never heard.
5 · Comparing
One row is blanked
Each man sends the whole sheet. Tent 3 receives tent 2's sheet with no row 4, and blanks row 4 in its own. Everyone waited for tent 2, so every sheet now matches tent 2's.
6 · Committing
All three commit alike
Each man commits to the first row that is not blank: row 1, attack. All three agree, on an answer someone sighted, though a man was killed and the slates chalked living men.
The arrangement turns on the man nobody chalks. Since nobody chalks that man, everybody waits for every one of that man's birds, so whatever the man has learned by a round, everyone who finishes the next round has learned too. By the end of spreading, every sheet that finishes holds everything that man's sheet holds.
In comparing, everyone waits for that man's sheet and blanks every row that is blank in it. A row filled in it is filled in every sheet, so nobody blanks it. Everyone who reaches the end therefore holds exactly that man's sheet, which is not empty, since it holds the man's own sighting. All commit to the same answer, and it is an answer someone sighted.
Nobody waits for ever, because a dead man is chalked in the end and a live man's bird comes in the end. So every man who lives commits, and all three demands are met. Nobody is in charge of any of it. Everybody sends everything to everybody, and the man who holds it together is one nobody can name.
The night above was a single night. Press a button below for another, with as many deaths as you choose, and check that the living always end with one sheet.
Another night choose how many are killed
Each press deals new sightings, new deaths and new mistaken marks, and runs the arrangement by its rules.
A slate that never, from dusk on, chalks one living man is a great deal to ask. A slate may be right about someone only in the end, and it remains to see what the four can do with that.
Proof · that with a strong slate everyone who finishes holds the same sheet
Theorem 2. With a failure detector of class S, consensus is solvable whatever the number of crashes. Here n = 4; Vp is the sheet of p (a blank is ⊥); the algorithm is that of Fig. 5, §6.1, with n − 1 = 3 rounds of Phase 1, then Phase 2, then Phase 3.
Every row of every sheet is either blank or that tent's true sighting, since sightings are
only ever copied.
Let c be the man never chalked. Everyone who finishes a round received
c's bird for that round, having waited for it.
After spreading, every finished sheet holds all of c's. Take a sighting
c first learned in round r. If r is before the last round,
c sends it in round r + 1 and everyone who finishes that round has it. If
r is the last round, three rounds among four men means the sighting reached
c through every other man, each of whom wrote it into a sheet before passing it on.
After comparing, every finished sheet equals c's. A row filled in
c's sheet is filled in every sheet sent in comparing, by the last step, so nobody
blanks it. A row blank in c's is blanked by everyone, since everyone waits for
c's sheet.
c's own row is filled in c's sheet and so in everyone's, so every
finished sheet has a first filled row, the same in all. Everyone who commits, commits to that tent's
sighting.
Nobody waits for ever, since a dead man is in the end chalked by every living man and a live
man's birds all arrive. So every living man commits.∎
Slates right only in the end
In the end, one man spared
Slates that are right about someone only in the end are the slates in the end strong. For as long as such slates like, every man may be chalked by everyone. Only from some moment nobody sees is one living man left alone. The four can still agree, provided more than half of them live. With four men, one may die.
The sheets leaned from dusk on a man nobody chalked, and now there may be no such man until late in the night. So the four take turns, and each tent in its turn tries to bring the rest to one answer. Each round belongs to one tent, in number order: 1, 2, 3, 4, then 1 again. Nobody commands this. The round number alone decides whose turn it is, as on the windy nights.* Each man carries an estimate, an answer, which starts as the sighting, and beside it the round in which the man last took it up. A round has four steps.
(1) Every man sends the round's owner the estimate and the round it was taken up.
(2) The owner waits for three of these, its own included, and takes the estimate taken up most recently. The owner sends it to every tent.
(3) Every man waits for the owner's estimate, or until the man chalks the owner. If the estimate comes, the man takes it up, notes this round, and sends the owner agreed. If the owner is chalked first, the man sends not agreed.
(4) The owner waits for three replies. If all three say agreed, the owner sends every tent a parting bird naming the estimate.
Committing. A man who takes in a parting bird for the first time sends it on to every tent, then commits to its answer.
Choose a night and take the rounds one at a time. For the first two rounds the slates are wrong and a man may chalk an owner who lives. From the third round they are right. Watch which rounds come to nothing, and whether one sends out the parting bird.
Rounds by turns choose a night
Choose a night.
The four never commit to two answers. Take the first round in which three men sent agreed, say on hold. Those three took up hold in that round. Any later owner waits for three estimates, and any three out of four share a man with those three, so the owner sees at least one hold taken up that recently or later. Take the estimate taken up most recently, and by the same argument round after round, it is hold. So every later owner sends hold, and every parting bird names hold.
Every living man commits. Nobody waits for ever, because a dead owner is in the end chalked, and three men live to reply. From some moment one living man is never chalked. When that man's turn next comes, the man gathers three estimates, everyone waits for the estimate, nobody chalks the owner, all say agreed, and the parting bird goes out. Each man who takes it in sends it on before committing, so it reaches every man who lives.
While the slates are still chalking the living, rounds fail: a man chalks a live owner whose bird is slow, says not agreed, and the round comes to nothing. Failing is always safe, since a round that fails sends out no parting bird. The chalk can cost time. It can never cost agreement.
A strong slate bore any number of deaths, and this one needs more than half alive, because an owner must gather three estimates and three replies. That may be a weakness of the turns, or it may be a need that every arrangement shares.
Proof · that the turns never commit anyone to two answers, and in the end commit everyone to one
Theorem 3. With a failure detector of class ◇S, consensus is solvable if fewer than n/2 processes crash. Here n = 4, so three is ⌈(n + 1)/2⌉; the algorithm is the rotating coordinator of Fig. 6, §6.2, and the parting bird is Reliable Broadcast of the decision (Fig. 4). Here e is an estimate, r a round, and q a process.
No two answers. Let r be the first round in which three men sent
agreed to its owner, on estimate e. Each of them took up e in
round r. Show by induction that every owner of a round k ≥ r
who sends an estimate sends e. For k = r it is so. For later
k, the owner heard from three men; one of them is among the three of round
r, and reported an estimate taken up in round r or later. So the most
recent round t among the three satisfies r ≤ t <
k, and the estimate taken up in round t was sent by that round's owner,
which by induction was e.
Every parting bird was first sent by an owner who had three agreed in a round no
earlier than r, so every parting bird names e, and everyone who commits, commits to
e. Every estimate is someone's sighting, so e was sighted.
Committing. If anyone living takes in a parting bird, that man sends it on before committing, so every
living man takes it in and commits. Suppose instead nobody living ever commits. No living man is stuck
for ever in any round: three men live to send estimates and replies, and a man waiting on an
owner either gets the owner's estimate or, if the owner is dead, in the end chalks the owner.
From some time, one living man q is chalked by nobody, and the dead are all dead.
Take a later round whose owner is q. q gathers three estimates and sends one;
everyone waits for it, since nobody chalks q; three reply agreed; q sends a parting bird. That contradicts the supposition.∎
Would every arrangement need it?
Why more than half, then
The need for more than half alive is shared by every arrangement. It holds even for slates in the end perfect, which in the end chalk the dead and nobody else. To see it, suppose some arrangement carried the four past two deaths, and run it on three nights.
Take the nights in turn. On each, look at what tents 1 and 2 can see of tents 3 and 4, and at what the two pairs commit to.
Three nights pairs: tents 1 and 2, tents 3 and 4
Each line is one tent, and each ring further out is a later moment. A hollow dot is a man who has not committed; a filled dot is one who has, blue for hold and red for attack. A cross is a dead man.
On the third night nobody is dead, but each pair's birds to the other are slow and each pair chalks the other, exactly as on a night when the other pair was dead. The slates are rubbed clean afterwards, too late. If two of the four may die, no arrangement meets the three demands, even with slates in the end perfect.
The difference from a strong slate is when the slate is right. A strong slate never chalks one living man, from dusk, and that man holds the four together from the start. A slate that is right only in the end may be wrong about everyone for as long as the arrangement needs it to be right. While it is, the four are two pairs, each able to believe the other dead.
So a slate in the end strong, with more than half alive, is enough, and with such slates the half cannot be spared. Nothing so far has said where such a slate comes from, or what its promises leave unsaid.
Proof · that slates in the end perfect cannot carry the four past two deaths
Theorem 5. Consensus cannot be solved using a failure detector of class ◇P if f ≥ n/2, where f is the number of processes that may crash. Here n = 4 and f = 2; the three nights are the runs R₀, R₁ and RA, and A and B are times defined in the steps.
Suppose some arrangement does. Divide the four into pairs: Numbers 1 and 2, Numbers 3
and 4.
The first night. All sighted hold. Numbers 3 and 4 are dead from dusk, and
the other two chalk them all night. That slate is in the end perfect. Numbers 1 and 2 commit,
within some time A, and to hold, since only hold was sighted.
The second night. The same with pairs and answers swapped: Numbers 3 and 4 commit
to attack within some time B.
The third night. Numbers 1 and 2 sighted hold, Numbers 3 and 4 attack.
Nobody dies. Every bird between the pairs sits in the pines until after A and
B, and until then each pair chalks the other; after that, all birds arrive and all
chalk is rubbed out. That slate is in the end perfect too.
Until then each pair sees exactly what it saw on its own night, and commits: one pair to hold,
the other to attack. That contradicts the first demand.∎
Granted, not earned
What the slate does not say
Where a slate comes from is the one thing the slate does not say. Its promises are granted, not earned. On a night when no bird has a longest flight, and nothing more is known, no man can keep a slate that is even in the end weak. If one could, the four could agree on that night, and they cannot.*
So the slates of this book are an assumption about the hill, stated as a promise about chalk. The four were handed slates that keep their promises, and were never told how to keep one.
A slate can be kept on a windy night. Where a wind blows for a while and then drops, and in still air every bird comes within a glass,* a man can keep a slate in the end perfect. Every man sends a bird to every tent, again and again, to say the sender is alive. A man chalks a tent when a glass has run out with no bird from it. When a bird from it comes after all, the man rubs out the mark and waits longer for that tent next time. Below, one man watches one tent through such a night. Run it once with the watched man alive and once with the watched man killed.
A slate kept on a windy night one watched man
Each cell is one moment, later to the right. Blue cells are the windy part of the night, when a bird may take any time. A dot is a bird taken in, a cross is a mark standing against the watched man, and a loop is a mark rubbed out.
The delays are drawn at random for the picture; the rule the watcher follows is the one in the text.
Each mistaken mark lengthens the wait. Once the wind has dropped, a live man's birds come in time once the waiting is long enough, so in the end nobody living is chalked. A dead man's birds stop, so the dead man is chalked for good. The slate is a way of saying what the wind gives, without saying anything about wind.
Three more things about the slates are worth setting down before leaving the hill.
A slate that breaks every promise
Still never two answers
If the slates chalk the living for ever and never chalk the dead, the two arrangements may never commit anyone. They never commit two men to different answers. Only committing is lost.
The weakest slate that will do
In the end weak
In the end weak, with more than half alive, is enough. It is also necessary: any slate with which the four could agree can be made into one in the end weak. That was proved separately, and is not proved here.
Many things to decide
The same slates
If the four had many things to decide, one after another, and had to take them in the same order, the same slates would do, and nothing weaker: agreeing once and agreeing on an order can each be turned into the other.
Nothing follows here from committing. The four attack together or hold together, and what happens then is not the subject of this book.
Back to machines
At the foot, in the paper
Read the foot of the hill again with machines in the tents, and the slates can be checked against the paper of Chandra and Toueg. Every man is a process, a man killed is a process that has crashed, and the slate is a failure detector. Hover over a row, or tap it, to see who is who.
At the foot of the hill
In the machine room
A failure detector may be wrong, often, and still be enough: with one correct process never suspected, consensus survives any number of crashes, and if that holds only eventually, it survives as long as a majority is alive.
Consensus is impossible in an asynchronous system with even one crash because a crashed process cannot be told from a slow one. The detector takes exactly that obstacle and asks how well it must be overcome.
The paper behind this book. Tushar Deepak Chandra and Sam Toueg, Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the ACM 43, 2 (March 1996), 225–267. The eight classes, the reduction from weak to strong completeness, consensus with S and with ◇S, the majority lower bound, and the equivalence with atomic broadcast.
The ideas, plainly. Consensus is impossible in an asynchronous system with even one crash, because a crashed process cannot be told from a slow one. Chandra and Toueg add an unreliable failure detector: a module at each process that lists the processes it suspects, and may be wrong. They classify detectors by completeness (crashed processes are eventually suspected, by every or by some correct process) and accuracy (correct processes are not suspected: never, or eventually; all of them, or at least one).
Weak completeness can be turned into strong by gossiping suspicions, so four classes matter. With S, where some correct process is never suspected, consensus tolerates any number of crashes, by relaying proposals for n − 1 rounds. With ◇S, where some correct process is eventually never suspected, consensus needs a majority of correct processes and uses a rotating coordinator; safety holds however badly the detector behaves, and progress returns once it behaves. The majority is necessary even with ◇P, by a partition argument.
A failure detector packages timing assumptions as a statement about suspicions. In partially synchronous systems, growing timeouts implement ◇P; the detector lets algorithms be written without mentioning time at all. ◇W is the weakest detector for consensus, and consensus is equivalent to atomic broadcast.
