Can a replicated service keep its commands in order when some of its machines lie, the leader included, and messages take arbitrarily long?
We find out by exploring how four bandits holding a hilltop held one book of their loot when any of them, their chief included, might be lying.
After Miguel Castro and Barbara Liskov, Practical Byzantine Fault Tolerance, 1999
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 service is run on several computers, so that it survives the loss of some. Every honest copy must apply the same commands in the same order, even when some copies lie.
The order matters because the effect of a command depends on the commands before it, as the two copies beside this show. A faulty machine here may do worse than stop. It may lie, and the leader that hands out the order may be the one lying. Up to f of 3f + 1 machines may be faulty, which with four machines is one. Messages may take any time at all, so the order must hold whatever the delays, and progress is asked for only once delays stop growing without bound.
The first keeps the order under one leader, and the second carries it from one leader to the next. We tell it with four bandits, a scroll of their loot, and trained rats.
Two copies of a service both hold 3. Two commands arrive: add 1, and double it.
Number 1, the chief, sits inside the ring wall with the loot, and Numbers 2, 3 and 4 hold posts out on the slopes, none in sight of another.* One of the four may lie, and with four bandits one is as many as the others can allow for.
The four hold a scroll of the loot, one copy at each post, since no post is in sight of another. The scroll says where each strongbox lies, and whose share it is.
The scroll grows by entries. An entry is one record about the loot, the third strongbox lies in the north cleft or the silver cups are Number 3's share, and any bandit may file one. Every copy must take the entries in the same order, because the effect of an entry depends on what the scroll already says. Two copies that took the same entries in different orders could come to say different things about the same strongbox.
These are later nights of the siege. The sandglasses were turned together once, on the first night, and never again.*
The four owe each other two things about this scroll, and the two are owed on different terms.
Every honest copy takes the same entries in the same order. The scroll then behaves as though one hand wrote every entry at a single moment between its filing and its standing.*
Every entry that an honest bandit files stands in the end, once the wind has dropped for long enough.
Order must hold in any wind, because nobody can see the wind drop. Going on cannot be promised while the wind blows. If four bandits could promise to agree on anything with the rats held in their holes for any time, the mercenaries at the foot could agree whether to attack, and they cannot.*
Four copies, then, with one liar among the four and a wind that nobody can see drop. Something has to decide what order the entries go in.
Safety: the service is linearizable. Liveness: clients eventually receive replies, provided at most ⌊(n − 1)/3⌋ replicas are faulty and delay(t) does not grow faster than t indefinitely. (Castro and Liskov, §2–3.)
The order of the entries is decided by numbering them, so that every copy can take them in number order. Numbering is a job, taken by one bandit at a time. The job does not belong to the chief by right, because on the crown the chief is a job and no rank.*
The job starts with Number 1, the chief inside the ring wall. When it passes, it passes in number order: 1, 2, 3, 4, then 1 again. Each spell in the job is a term, and terms are counted, so the count alone says who has the job.
A bandit who wants an entry seals it and sends it to the registrar. The registrar gives it the next number. Then the others make sure of it, and at the end every honest bandit writes the entry into their copy, in number order, and sends the filer a sealed word that it stands.
Anyone may have the job, the one who lies included, so nothing the registrar says is trusted on its own. Everything that follows is built against a registrar who does any of three things.
Two different entries go out under one number.
One entry goes to some bandits, and another to the rest.
The entry is filed, and the registrar numbers nothing.
A bandit knows their entry stands when it stands in their own copy. The paper has a rule for a filer who is not one of the four, which is to wait for two matching sealed words from different bandits. With one liar, two matching words include an honest one. The four do not need that rule, since each honest bandit holds a copy and can read it. The rule is what a filer from outside the four would need, and there is none.
The registrar may lie, then, in any of these three ways. The others need a way to make sure of a number before they write anything down.
The others make sure of a number by echoing it, twice. An entry stands only after the registrar has numbered it and the bandits have echoed it twice. Every rat here is sealed, and every bandit holds every sealed rat they take in, so that each can later show what they were told. Follow one entry from its filing to its standing, and watch how many seals each post holds. Scroll slowly: the picture moves with you.
Number 2 wants an entry written. They seal it and send it to the registrar, Number 1.
The registrar gives the entry a number, 7, and sends the numbering to the others. The wind holds back the rat to Number 4, and nobody waits for it.
Numbers 2 and 3 accept it. Each tells the others: in this term, I heard that entry 7 is this one.
A bandit who holds the numbering and two matching first echoes, from bandits other than the registrar, has the entry readied. Numbers 1, 2 and 3 now do.
Each bandit with the entry readied tells the others: in this term, entry 7 is readied here.
A bandit with three matching second echoes, their own among them, has the entry standing. It stands at Numbers 1, 2 and 3, and nobody waited for Number 4.
A bandit writes a standing entry into their copy as soon as every lower number has been written, and sends the filer word that it stands. Rats may come in any order, so entry 9 can stand before entry 8. A bandit then holds entry 9 and waits, and writes nothing past a gap.
An entry stands without waiting for everyone. Each step needs three matching seals out of four, so a post whose rats are held by the wind, or a liar who says nothing, cannot hold the others up.
The two echoes do different work. The first settles order within a term: once an entry is readied anywhere honest, no honest bandit can ready a different entry under the same number in that term, even if the registrar lies. The second settles it across terms: once an entry stands at an honest post, enough honest bandits have it readied that any later registrar will be made to keep it.
Both claims rest on three matching seals being enough, and one of the three seals may be the liar's.
In the paper's terms the registrar is the primary, the numbering a pre-prepare, the first echo a prepare, readied is prepared (the pre-prepare and 2f matching prepares), the second echo a commit, and standing is committed-local (prepared and 2f + 1 matching commits). Writing in number order is execution in sequence-number order. (Castro and Liskov, §4.2.)
Three matching seals are enough, even with the seal of a liar among them, because any two groups of three, out of four, share two bandits. At most one of those two lies, so the two groups share an honest bandit.
Suppose a lying registrar tells two bandits that entry 7 is X and the others that it is Y. For X to be readied at an honest post, three bandits sealed X for number 7 in this term. For Y to be readied, three sealed Y. The two threes share an honest bandit, and an honest bandit seals only one entry for a number in a term. So X and Y cannot both be readied.
Try it on the crown below. Choose which bandit each group leaves out and which one is supposed to lie, and watch who is left in both groups. Then take one bandit away, and see that groups drawn from three can fail.
In any term, no two different entries are readied under the same number at honest posts.
In the paper's terms an entry is a request m, a term is a view v, a number is a sequence number n, and there are four replicas (3f + 1 with f = 1). Invariant of §4.2. If prepared(m, v, n, i) is true, then prepared(m′, v, n, j) is false for every non-faulty replica j and every m′ ≠ m.
Four bandits are the fewest that will do for one liar. A bandit can never wait to hear from everyone, since one may be a liar who keeps quiet. So a bandit acts on hearing from all but one, which is three. But the one not heard from may be an honest bandit whose rat is held in its hole, and then the liar may be among the three heard. The honest must still outnumber the liars among those three: two honest against one liar. That needs four bandits for one liar, and in general more than three times as many as may lie.* Seals do not lower the number. A seal stops a liar forging the word of another bandit. It cannot make a liar answer promptly with their own.
Within a term, then, a lying registrar cannot number one place two ways. A registrar can still number nothing at all.
A registrar who numbers nothing leaves every filed entry waiting, and then the job must pass. Nobody can tell a registrar who stalls from one whose rats are held by the wind, so the bandits do not judge. Each simply stops waiting.
A bandit who has an entry filed that has not yet stood turns their sandglass. If it runs out first, they ask for a change: they stop taking part in this term and send every bandit a sealed request for the next term. The request carries the proof of every entry readied at their post, each a numbering and two first echoes.
In the picture below, file an entry and then choose what the registrar does, once with the wind blowing and once with it dropped. Watch for the two cases that look the same from every post.
The crown from above. The registrar has the thick outline. Each press is one thing that can happen in a term.
An entry is filed and waits to be numbered. The wind is blowing.
The next registrar waits for requests for the new term from three bandits, their own among them, and sends every bandit the three requests and a new numbering. The requests decide the new numbering, and the registrar has no choice in it. For each number, if some request shows an entry readied there, the registrar numbers the one readied in the latest term. If none does, the registrar numbers a blank entry, which does nothing. Each bandit checks that the requests are sealed and that the new numbering is what they call for, then echoes it twice, as before, in the new term.
A new registrar cannot drop an entry that already stood. Suppose an entry X stands at some honest post as number 7. Then three bandits sent second echoes for it, of whom at least two are honest, and X is readied at those two. The new registrar must show three requests, and three requests out of four always include one from those two. That request shows X readied under number 7, so the new registrar must number X under 7 again. Try it: choose who sent the second echoes, who is supposed to lie, and whose request the new registrar leaves out.
If an entry stands under a number at any honest post, every honest post that ever has an entry stand under that number has the same one, whatever terms they stood in.
In the paper's terms: §4.5.1. Non-faulty replicas agree on the sequence numbers of requests that commit locally, even if they commit in different views at different replicas. Let committed-local(m, v, n, i) hold when prepared(m, v, n, i) and 2f + 1 matching commits are held; the paper gives this argument as a sketch.
The paper's proof is a sketch, with the full argument in Castro's thesis. This version leaves out the settled checkpoints described below, which let a request show a settled checkpoint in place of the entries below it.
In the paper's terms: view-change with the set P of prepared certificates; new-view with 2f + 1 view-changes and the set O of pre-prepares; null requests fill gaps. (Castro and Liskov, §4.4.)
Two more rules keep the job from passing too late or too easily. A bandit who sees requests from two others for a later term joins them, even before their own sandglass runs out, so an honest minority is not left behind. And no single bandit can force a change, because a change needs three requests and a liar alone can send only one. A lying registrar can make their own term fail by stalling, but the job then passes, and with four bandits a liar holds it for at most one term in a row.
A stalled term ends this way whatever stalled it. While the wind blows, though, sandglasses run out on honest registrars too, and the job passes again and again.
The job passes again and again while the wind blows, because sandglasses run out on honest registrars whose rats are merely pinned. Nothing stands, and nothing wrong stands either. Once the wind has dropped the changes must stop, or no entry would ever stand.
The changes stop because each bandit doubles their sandglass at every change. A bandit who asked for a change and does not see the new term work within their sandglass asks for the next one, but waits twice as long before asking for the one after. In the end the sandglasses are longer than a whole term's worth of short runs. Then the first honest registrar of a term that begins in still air numbers the waiting entries, the echoes come back in time, and the entries stand.
Pick a sandglass and a wind below and run the nights. Compare the doubling sandglass with one that stays the same, and see in which term the entries stand.
Every registrar is honest in this picture, and the first sandglass is the time a short run takes at most. A term's worth is counted as three short runs: the numbering and the two echoes.
If the wind, once it drops, stays down long enough, every entry an honest bandit files in the end stands.
The paper puts precisely how long the wind must stay down: the time a rat takes must not go on growing faster than the nights themselves pass. The doubling sandglass outgrows any delay that does not keep outgrowing it. The paper argues this in outline, and its full proof is in Castro's thesis.
In the paper's terms the time a rat takes, counted from its first sending and with resending, is delay(t), and it must not grow faster than t indefinitely. The view-change timeout doubles at each view change. (Castro and Liskov, §2 and §4.5.2.)
The scroll now keeps its order and goes on. One cost is left. Every bandit holds every sealed rat, since a change of job may call for them, and the store grows with every entry.
The store of sealed rats need not grow for ever. Every hundred entries, each bandit seals a short summary of their copy up to that number and sends it to everyone. When a bandit holds three matching summaries for the same number, that point is a settled checkpoint: at least two honest bandits have the same scroll up to there.
A settled checkpoint lets a bandit throw away every echo for numbers up to it, since the three summaries now stand for those entries. A bandit whose copy fell behind can take the settled checkpoint from any of the three and trust it. The settled checkpoint also bounds the numbering. A registrar may use only numbers from the last settled checkpoint up to some fixed distance beyond it, so a lying registrar cannot use up the numbers by jumping to an enormous one.
In the picture below, let entries stand until the allowed numbers are used up, then settle a checkpoint, and see which numbers a registrar may and may not use.
Nothing is written yet. The picture's allowed numbers run two hundred beyond the last settled checkpoint.
In the paper's terms: checkpoints every K requests; a stable checkpoint needs 2f + 1 matching checkpoint messages; low and high water marks h and H = h + k. (Castro and Liskov, §4.3.)
The four now have order in any wind, progress once it drops, and a store that does not grow without end. It remains to say what the arrangement leaves unprotected.
The arrangement leaves several things unprotected, and each is better said plainly than left for a reader to find. Here are six questions a reader might ask of the loot scroll, and the answer to each.
Nothing stands while it blows. Order holds in any wind, and going on waits for the wind to drop and stay down. That is no weakness of this arrangement, because no arrangement could do better.
A liar can. The scroll keeps the entries in order and does nothing for the sense in them. An entry that makes no sense stands in the same place in every honest copy if a bandit may file it. Which entries a bandit may file is for the four to arrange themselves.
Nobody does, and the arrangement never needs to know. It works if any one of the four lies, and it never names them. A stalled term might be a liar or the wind.
Nothing is kept secret. Every bandit holds the whole scroll, and may show it to anyone.
Seals are costly, and the paper spends them sparingly. Every rat here is sealed. The paper's fast version seals only the requests for a change of job and the new numbering, and marks everything else with cheaper marks that the receiver alone can check. The order kept is the same.
Nothing. The scroll says where the loot lies and whose it is. What the four do with it is not the subject of this book.
Read the crown again with machines at the four posts. Every bandit is a replica, every rat is a message, and the registrar is the leader that numbers the commands. Hover over a row, or tap it, to see who is who, and where the paper says it.
A service on 3f + 1 machines keeps every honest copy in the same order whatever the delays and whoever lies, and goes on once delays stop growing.
Safety needs no timing assumption at all. Progress needs only that message delays do not grow without bound.
In practice, cheap message authentication codes replace most signatures.
Setting The Crown of Mount Phyle
The paper behind this book. Miguel Castro and Barbara Liskov, Practical Byzantine Fault Tolerance. Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI), New Orleans, February 1999. The three-phase protocol, view changes, checkpoints, the liveness argument and the MAC-based optimization.
The ideas. Castro and Liskov give a state machine replication protocol that tolerates f Byzantine replicas out of 3f + 1, keeps safety with no timing assumptions at all, and makes progress once message delays stop growing without bound.
In each view one replica is the primary and assigns sequence numbers. Replicas then echo twice. The prepare phase, completed when 2f + 1 replicas vouch for the same request and number, fixes the order within a view even if the primary lies, because any two quorums of 2f + 1 share an honest replica. The commit phase, also 2f + 1, ensures that a request committed anywhere was prepared at enough honest replicas that every later view must carry it forward.
When the primary seems stuck, replicas time out and move to the next view, sending proof of what they prepared; the new primary must re-propose it. Doubling timeouts and joining view changes on f + 1 requests keep the system from changing views forever once delays are bounded. Checkpoints bound the log. In practice, cheap message authentication codes replace most signatures.
Castro, M., and Liskov, B. Practical Byzantine fault tolerance. Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI), New Orleans, February 1999.