One Leader at a Time

Where this book sits

This book retells

Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed SystemsOki & Liskov 1988

Leads to

Practical Byzantine Fault ToleranceCastro & Liskov 1999 · Keeping Order Among Liars
- primary and view changeA primary, its backups, and a view change that replaces a faulty primary.
Viewstamped Replication RevisitedLiskov & Cowling 2012
- the protocolThe protocol, restated without transactions.
In Search of an Understandable Consensus AlgorithmOngaro & Ousterhout 2014
- leader and termsA strong leader, and terms numbered as views are.

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

One primary, and what happens when it goes

A service is kept on several machines, so that it outlives the loss of some of them. One machine, the primary, orders every operation and sends it to the others, the backups.

The trouble comes when the primary goes. Machines crash and come back, sometimes having lost what they held, and messages are slow or lost, though no machine lies. Viewstamped Replication, which Oki and Liskov published in 1988, gets through it on two rules.

An operation is committed once a majority of the machines hold it.
A new primary starts from the fullest log a majority can show.

Together they mean that nothing committed is ever lost. We tell it with five legislators in a round hall who keep one law, and a podium that only one of them may write from.

Five machines, one primary

The primary takes operations and sends them on. Green ones are held by a majority.

The Tholos from its paved court: a round stone hall under a conical tiled roof with a small lantern, a gabled porch before its door, and four figures in blue-grey, saffron, madder red and green coming and going, each alone

The Tholos of Schedia

Five legislators, one law

Schedia, the city on the eastern arm of Paxos, keeps its own law. The law is made in the Tholos, a round hall where nobody can be heard across the floor, so everything goes by messenger.^*

Slow messengersMessengers are slow, and some never arrive.

Stepping out, going homeA legislator may step out for a while, or go home and come back later.

Nobody liesWhatever a legislator writes or answers is true, and nobody forges a note.

What is kept

The council and its law

The council has five legislators. Each keeps a copy of the law on wax tablets, at a bench of their own.

The law is a list of lines, written one after another: harbour dues are two obols a hull; the cove is closed to nets in spring; the dues above are halved for boats of Schedia. Every copy must hold the same lines in the same order, because a line can depend on the lines before it. The halving means nothing without the dues it halves.

Legislators come and go, and their messengers are slow. Through all of it the council owes the city two things.

What the council owes the city

One law

The five copies behave as a single record kept in a single place. A citizen never sees two different laws standing in the same place.

What the council owes the city

Passed stays passed

Once a law has passed, it stands for good, in its place, whoever holds the podium afterwards.

Five copies, then, and legislators forever coming and going. Somebody has to decide what goes into the law, and in what order.

In the paper · the group and its failures

A module group of cohorts behaves as a single logical entity; nodes crash (fail-stop) and recover; the network may lose, delay, duplicate and reorder messages and may partition; failures are not Byzantine. Events known to a majority of cohorts survive view changes. §1–2, §4.

Who decides what goes in

The podium

What goes into the law is decided at the podium. It stands at the centre of the Tholos, and one legislator at a time holds it: the holder. Only the holder adds lines to the law.

The podium is no pulpit, since nobody can be heard from it either. It is an office. The holder writes each line at the desk and gives it the next number, and the others copy what they are sent and do nothing else with the law. Three kinds of work pass through it.

At the podium a figure in saffron writes at the desk beside a board on its post while two young runners set off in different directions towards benches where council members wait

The podium's work

Writing

The holder weighs each petition, writes the lines it calls for, numbers each in turn and gives it to the runners.

The podium's work

Running

Each bench has its own runner, who brings it the lines in the order they were written and never skips one. A runner may be held up, but a bench that holds line 12 always holds lines 1 to 11 as well.

The podium's work

Petitions

Citizens at the doors send petitions to the podium: new dues, a closed season, a ruling on a quay. A petition that reaches a bench instead is sent back with the holder's name.

The holder writes a line and hands it to the runners. The petitioner is still waiting at the door, and the holder has to know when it is safe to answer that the petition is law.

In the paper · primary, backups and the communication buffer

The primary executes calls; backups are passive and receive event records. The communication buffer delivers event records reliably, in timestamp order, to every backup in the view; a failure to deliver leads to a view change. A cohort that is not the active primary rejects calls with the current viewid and primary. §2, §3.3.

When the holder may say “it is law”

When a law passes

A petition becomes law when its line is safe, and a line is safe once a majority of the council hold it. That is three of the five: the holder and two others.

So the holder does not wait for everyone. Each runner comes back with the bench's word, I hold everything up to line 12. As soon as two benches have said so, line 12 passes, and only then does the holder answer the petitioner. Here Okios holds the podium, and Theron has stepped out.

The runners go out and come back with a word

The Tholos from above. The ringed legislator holds the podium. Click a bench to have its legislator step out of reach, or come back.

11last line written11passed up to

Okios holds the podium. Theron has stepped out. Write the next line.

Passed means three hold it

A law has passed when its line, and every line before it, is held by the holder and at least two others

Three is the right number for two reasons. Someone is nearly always out of reach, and a council that waited for all five would pass nothing. And the holder may be gone tomorrow, when the next holder will start from what a majority can show. Any two majorities of five share a legislator, as any two majorities in the Chamber across the bay share a member.^* So a line that three hold is always found again.

Lines that no majority holds yet are drafts. A change of holder may lose them, and that does no harm, because nobody was told they were law.

The holder numbers the lines, but holders change. A number written under one holder has to be told apart from the same number written under the next.

In the paper · waiting for a sub-majority

force-to(v) waits until a sub-majority of backups, one fewer than a majority of the configuration, know every event of the current view up to v.ts; with the primary, a majority then knows it. §3. In the paper the moments that must wait are a transaction's prepare and commit; this book, keeping one law, has only one, the passing of a law.

Numbers that survive a change of holder

Board and line

A line's number means something only under one holder. So every spell at the podium gets a mark of its own: a board, which hangs on its post beside the desk.

A board bears a count and the name of the legislator who raised it: board 7, Liskovia. Boards are ordered by count, and two with the same count by name, in the order of the alphabet. Each legislator raises boards only in their own name, so no two boards are ever the same.

Line numbers start again under every board, so a line is known by board and line. The later board is always the later mark, and under one board the higher line is the later. Each legislator also keeps a note in the margin of their tablets: for every board they have served under, the last line they hold.

Which is the later? choose two marks

Choose any two.

The later line knows more

A later mark holds everything an earlier one does

Under one board this is so because runners never skip a line: whoever holds a later line holds every earlier one. Across boards it is so because every board opens with its holder sending out the whole law, so whoever holds any line of a later board holds everything that board started with. A higher line number proves nothing by itself. Board 6, line 40 may hold far more lines than board 7, line 1, and it is still the older copy.

A board changes when the podium falls silent. Somebody has to notice, and then do something about it.

In the paper · viewids and viewstamps

viewid = ⟨cnt, mid⟩, totally ordered and unique to its creator; a timestamp, unique and ordered within a view; viewstamp = ⟨viewid, ts⟩; each cohort's history is a sequence of viewstamps, one per viewid, and its state reflects exactly the events up to each. §2, Figures 1 and 4.

Who notices, and what they do

An empty podium

A silent podium is noticed through the roll. Every so often each legislator sends each of the others a note, I am here.

A legislator who stops hearing from someone, or hears again from someone who was away, or has just come back from home, calls for a new board and is its caller. The silent one may have gone home, or stepped out, or their notes may only be slow. The caller cannot tell and does not need to, because a board is called either way.

The caller takes a count higher than any board they have seen, adds their own name, and sends every legislator an invitation. A legislator invited to a board higher than any they have seen accepts it, stops working under the old board, and answers in one of two ways.

A figure in green sits writing on small wax tablets with a blank board propped beside him and two young runners waiting; across the floor the podium's seat and desk stand empty

The two answers

With tablets

I hold up to board 6, line 40, and whether they held the podium under board 6.

The two answers

Without

I have lost my tablets. My bench says board 6.

Two legislators may call at once. Then the higher board wins: the lower caller is invited to it, accepts it, and answers like anyone else. Several callers slow the council down, but they never confuse it.

Invitations go out and answers come in. The caller now has to judge when the new board may form, and who takes the podium.

In the paper · the view manager and its invitations

“I'm alive” messages; the view manager's invitations with a new viewid; a normal acceptance carries the cohort's viewstamp and whether it was primary, a crash-accept only its viewid. §4.

A change of board

Who takes the podium

A new board forms when a majority of the council has answered, and among the answers is someone sure to hold every law that has ever passed. While everyone keeps their tablets, the second follows from the first. Scroll slowly, and the picture moves with you.

1 · Board 6

Okios holds the podium

Line 12 has passed: Okios, Liskovia and Kleon hold it. Melissa and Theron hold up to line 10. Okios has written line 13, a draft that no bench holds yet.

2 · Silence

The roll goes unanswered

Okios steps out, and no note from him reaches the benches. Liskovia stops hearing from the podium.

3 · The caller

Liskovia calls board 7

She takes a count higher than any board she has seen, adds her own name, and sends every legislator an invitation.

4 · The answers

A majority answers, all with tablets

Kleon answers board 6, line 12. Melissa answers board 6, line 10. With Liskovia's own, that is three of five. Theron's answer is slow, and nobody waits for it.

5 · The holder

The latest board and line takes the podium

Three answers are a majority, and every passed law is held by three, so the two threes share someone. The answer showing the latest board and line therefore holds everything that passed. Here Liskovia and Kleon both show line 12, and Liskovia takes the podium.

6 · The opening line

The whole law, as the board's first line

Liskovia opens board 7 by sending every member the whole law as she holds it, with its notes. Melissa now holds everything that passed.

7 · A draft is lost

Okios comes back in

Okios sees board 7 and joins it. His tablets ran past the opening line with a draft that never passed, so he smooths line 13 away. Nobody was told it was law.

What passed survives

A law that passed under any board stands under every later board

If the old holder is among those with the latest line, the old holder is preferred, and nothing then changes but the board.

All of this supposed that everyone who answered still had their tablets. Some answers come without.

Sketch · that what passed survives, while everyone keeps their tablets

Write b and c for boards (views), ordered as boards are. A line has passed under b when the holder of b and two other members hold it and every line before it. Claim. A line that passed under b is held by every member of every board that forms after b.

The paper argues this informally (§2, §4); what follows is that argument, laid out by board.
Suppose a law's line passed under board b: the holder and two others held it, and every line before it.
The next board to form, c, formed on answers from a majority. Those answers and the three who held the law share at least one legislator, who answered with board b and a line at or past the law's line.
The new holder is the answerer with the latest board and line. By The Later Line Knows More, their copy holds everything the shared legislator's does, the law included.
Board c opens with the new holder's whole law, so every member of c holds the law, and any later line of c is written after it.
The same step carries the law from c to the board after, and so on to every later board.∎

A majority of answers is not always enough

When tablets are lost

An answer without tablets changes things. Take board 6 again, with line 12 passed and held by Okios, Liskovia and Kleon. Okios goes home and comes back to smooth wax, and Liskovia and Kleon step out. Okios, Melissa and Theron answer the next call, and three is a majority.

This board must not form. The only answers with tablets stop at line 10, and a board formed on them would start without a law the city was told had passed. So a lost tablet cannot simply be left out of the count. A board may form when a majority of the council has answered and one of three things also holds.

First

A majority still has its tablets

A majority of the whole council answered with tablets. The overlap works as before.

Second

The lost tablets were old

Every answer without tablets names an older board than the latest shown by an answer with tablets. Whatever passed before that older board ended was carried into every later one.

Third

The holder still has theirs

They name the same board, and that board's holder answered with tablets. Every line starts at the podium, so the holder's tablets cover anyone else's that were lost.

May board 7 form? set each answer

Board 6, held by Okios. Line 12 has passed: Okios, Liskovia and Kleon held it. Melissa and Theron held up to line 10.

Everyone here last served under board 6, so the second condition has nothing to apply to. The page has tried every one of the 243 ways the five can answer: whenever a board forms, its holder has line 12.

When no board may form, nothing happens for now. The caller waits and calls again. Once Liskovia or Kleon comes back within reach, a board forms, and line 12 is in it.

The old holder may have heard none of this, and may still believe the podium is theirs.

In the paper · when a view may form

A majority accepted, and (1) a majority accepted normally, or (2) crash-viewid < normal-viewid, or (3) crash-viewid = normal-viewid and the primary of that view accepted normally. The new primary is the cohort with the largest viewstamp, the old primary if possible. §4.

In the Tholos's porch a figure in blue-grey at a small stand hands a wax tablet to a young runner; through the doorway beyond, a figure in saffron sits at the podium's desk with a board on its post

Two who believe they hold the podium

The holder who has not noticed

Okios holds board 6 and steps out onto the porch. For a while no runner reaches him, and none of his reaches the benches. Inside, the others raise board 7 and Liskovia takes the podium. As far as Okios knows, board 6 still stands.

Two legislators now each believe they hold the podium, and nothing stops Okios from acting on it. The holding rides on the board's count, which every note carries, so he may go on taking petitions at the porch door and writing lines under board 6. Whether he can pass any of them is another matter.

Can Okios pass a line? board 6 on the porch, board 7 inside

Board 7 formed on a majority: Liskovia, Kleon and Melissa. Click Theron's bench to choose whether he has heard of board 7 yet.

1hold the line under board 6

Theron has not heard of board 7.

Two holders, one law

A holder who has missed a later board can still write lines, but can pass none of them

While it lasts, a citizen at the porch who asks Okios what the law says hears the answer of his copy, which may lack laws passed under board 7. He answers from what he holds and passes nothing new. As soon as a runner reaches him, or he walks back in, he sees board 7 and joins it.

So only a majority can pass a law, and only a holder's tablets can cover for lost ones. Both lean on enough legislators keeping what they hold.

In the paper · several active primaries

“The system performs correctly even if there are several active primaries … The old primary will not be able to prepare and commit user transactions, however, since it cannot force their effects to the backups.” §4.1.

What going home costs

Wax, not ink

Schedia keeps its law in wax. The tablets stay on the bench, and they are smoothed when their legislator goes home.

Only two things are cut into the bench's stone: the legislator's name, and the last board they served under, recut whenever a board forms. That is the stone. Stepping out keeps the tablets, and going home loses them. A legislator back from home knows their name and their last board and nothing of the law. They call for a new board at once, answer without tablets, and are brought up to date only by the new board's opening line.

Wax is quick, and cutting every line in stone would be slow, so Schedia counts on a majority remembering. See what that costs when too many go home on the same night.

A figure in grey sits on a stone bench against the Tholos wall with a wax tablet open on his knees, running a finger over the bare wax; a name in Greek letters is cut into the edge of the seat, and a stack of tablets lies on the stand beside it

Who goes home tonight? click a bench

Board 6 again, with line 12 passed. In the morning all five are back and answer the call for board 7. Those who went home answer without tablets.

Stopped, never wrong

Lost tablets can stop the council for ever. They can never make a board start without a law that passed

The paper names ways to make this rarer: keep a lasting record at the holder only, or give each member a supply that lets it write to lasting storage in the background. It leaves the choice to how much the law is worth.

Across the bay, the Parliament keeps its law in ink, and its Chamber has no podium. Each arrangement buys something the other lacks.

In the paper · what survives a crash

Most of a cohort's state is volatile. Only mymid, configuration and mygroupid, written when the cohort is created, and cur-viewid, written at the end of each view change, are on stable storage. A recovered cohort sets up-to-date to false and starts a view change. A catastrophe, a majority crashed at once, “does not cause a group to enter a new view missing some needed information. Rather, it causes the algorithm to never again form a new view.” §4, §4.2.

The other hall

Across the bay

The Parliament across the bay keeps the law of the rest of Paxos in a hall of the same kind: a rotunda where nobody can be heard, with legislators who come and go and messengers who take as long as they take.^*

The two laws never meet, since each covers its own city.^* So the two halls can be compared like with like.

What the Chamber's ink buys

It cannot be stopped by going home

A Paxon legislator writes the decrees in indelible ink in a scroll of their own, and a legislator back from any absence still has everything.^* Schedia's wax is quicker, and it asks that a majority not go home at once.

What Schedia's podium buys

One trip out and back passes a law

In the Chamber any legislator may start a ballot, and several may believe themselves president for a while, which costs time but never makes two scrolls disagree.^* In Schedia only the holder writes, the benches only copy, and a change of holder is a step of its own.

What the two halls share

Any two majorities share a legislator

The Chamber uses that fact for each decree's ballot. The Tholos uses it for each change of holder.

The two arrangements were found apart. Oki and Liskov published theirs in 1988; Lamport's account of the Parliament first circulated in 1989 and was not printed until 1998. That is why Schedia has a hall of its own on its own arm of the island.

The limits

What it does not say

The Tholos keeps every passed law through any change of holder. That is all it promises, and five questions show where the promise ends.

Does the council always get a new board in the end?

No. If notes keep going astray, a caller who stops waiting too soon forms a board without someone who could have answered, that legislator soon calls again, and the council can go on changing boards. The paper says so plainly and advises long waits and duplicate notes. Getting a new board is hoped for, not promised.

What of a petitioner who gets no answer?

They cannot tell whether their petition was written down before the holder fell silent, and sending it again to the new holder might put it in the law twice. The paper's answer is to abandon the whole piece of work rather than risk doing it twice.

Is one law the paper's case?

No. The paper builds all this for pieces of work that call on several councils and are settled together. There, work lost in a change of holder is abandoned. This telling keeps one council and one law, and lets the passing of a law stand for those moments.

Could a legislator lie?

Not here. Legislators stop, go home, come back and miss notes, but what they write and answer is true. Keeping order when some members lie is a harder task, with more members and more rounds of notes.

How does a citizen know who holds the podium?

They ask. A petition that reaches the wrong bench comes back with the holder's name. The paper leans on a directory, always available, that says who belongs to each council, and notes that no council can be more available than it.

Back to machines

The Tholos was a replicated service

Read the Tholos again with machines on the benches. Every legislator is a replica, the holder of the podium is the primary, and the law is the log they keep. Hover over a row, or tap it, to see who is who.

In the Tholos

In the machine room

One primary orders everything, and a new primary starts from the fullest log a majority can show, so nothing committed is ever lost.

Replicas that lose their state can stop the group for good. They can never make it go on with something missing.

Schedia and the Tholos, in detail All the papers

Setting Schedia and the Tholos

The paper behind this book

Brian M. Oki and Barbara H. Liskov, Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing (PODC), Toronto, August 1988, 8–17. — The primary copy method, viewstamps, forcing to a sub-majority, the view change algorithm and its formation rule, and transaction processing with two-phase commit.

The ideas, plainly.

Oki and Liskov replicate a service over a small group of machines that may crash, recover and be cut off from one another, but never lie. One machine, the primary, does all the work and sends a record of each step to the backups, in order. A step is safe once a majority of the group knows it, so the primary waits for enough backups before it tells anyone a result is final.

Each period with one primary is a view, named by a view number, and each step is stamped with the view and its position in it: a viewstamp. When the primary seems to be gone, or the group's members change, any member can call a view change. It collects the viewstamps of a majority, and the member with the latest one becomes the new primary and starts the view by sending its whole state. Because any two majorities overlap, and because a later viewstamp implies knowledge of everything earlier, whatever a majority knew survives.

The machines keep almost everything in memory, so a crash loses a member's state; three extra conditions stop a view from forming on answers that cannot show what was made final. If a majority lose their state at once, the group stops for good rather than go on with something missing. An old primary that has not noticed a change can do no harm, because it can no longer reach a majority.

Brian Oki and Barbara Liskov are credited as Okios and Liskovia. Kleon, Melissa and Theron are ordinary Greek names for seats no author fills. Schedia's legislators are told apart by colour: Okios blue-grey, Liskovia saffron, Kleon green, Melissa madder red, Theron grey.

In the paper, term by term

the council of five, each with a copy of the law	A module group of cohorts; the fixed set is the configuration; three or five is typical. §2.
the law; a line	The group state; an event record. §2–3.
slow or lost messengers; stepping out; going home	A network that loses, delays and reorders messages and partitions; a partition; a crash. No Byzantine faults. §1.
one law; passed stays passed	The group behaves as one logical entity; events known to a majority survive view changes. §2, §4.
the podium; the holder; the benches	The primary; the backups, passive. §2.
a runner who never skips a line	The communication buffer: reliable delivery in timestamp order. §2.
a petition; sent back with the holder's name	A call from a client; rejection with the current viewid and primary. §3.1, §3.3.
Passed Means Three Hold It; waiting for two	force-to: wait for a sub-majority of backups. §3. In the paper, at prepare and commit.
a board; its count and name	A view; viewid = ⟨cnt, mid⟩. §2.
board and line; the note	Viewstamp = ⟨viewid, ts⟩; the history. §2.
The Later Line Knows More	In-order delivery: a later viewstamp for a view implies knowledge of every earlier event in it. §4.
the roll; the caller; an invitation	“I'm alive” messages; the view manager; an invitation with a new viewid. §4.
an answer with tablets; without	A normal acceptance with the viewstamp; a crash-accept with the viewid. §4.
when a board may form	A majority accepted, and conditions (1)–(3). §4.
who takes the podium; the opening line	The largest viewstamp, the old primary if possible; the “newview” record with view, history and state. §4.
What Passed Survives	The paper's informal argument; here set out by board. §2, §4.
Two Holders, One Law	Several active primaries; the old one cannot force. §4.1.
wax; the stone	Volatile state; mymid, configuration, mygroupid and cur-viewid on stable storage. §4, §4.2.
coming back from home	up-to-date = false; the cohort starts a view change. §4.
Stopped, Never Wrong	A catastrophe means no new view is ever formed. §4.2.
no promise of a new board	The algorithm is “not tolerant of lost messages and slow responses”; long timeouts, duplicate messages. §4.1.
a petition with no answer	No reply: abort, since a retried call might run twice. §3.1.
the piece of work settled together	Transactions across groups, psets and two-phase commit. §3.
asking who holds the podium	The location server and each client's cache. §3.1.