Distributed Algorithms of Ancient Greece

Paxos · The Chamber

Consensus & Replicated State Machines

The Setting: The Chamber

The island of Paxos and Lamport's Chamber, where the book below is set. Read it first.

The Part-Time Parliament

How can a group of machines agree on a sequence of commands when any of them may wander off at any time, and no one is in charge for long?

Lamport answered this himself, with the part-time legislators of the Greek island of Paxos. We present his paper as he wrote it, with interactive figures. It is the paper that inspired this entire project. Lamport ends it with the parliament's fall; the other books set that aside, and in them the parliament is still sitting.

Lamport 1998 · Lamport 2001

Paxos · Schedia

Leader-Driven Consensus

Read this first

The Setting: Schedia and the Tholos

The city with laws of its own and the round hall it is governed from, where the book below is set. Read it first.

One Leader at a Time

Many systems put one leader in charge at a time. When the leader falls silent, how does another take over without losing anything the last one promised?

We find out by exploring how Schedia, a Greek city on Paxos with laws of its own, kept its law from a podium that one legislator held at a time, and how a new holder took over when the last one fell silent.

Oki & Liskov 1988

Arche · The Ring Road

Clocks, State & Linearizability

Read this first

The Setting: The Ring Road

The island, the three houses and the road between them, which every book here takes for granted. After it, the books below can be read in any order.

Ordering Without Clocks

If no two machines agree on the time, how can they agree on what happened first? And when two things happen far apart, how can anyone tell whether one led to the other or neither knew of the other?

We find out by exploring how ancient Greek trading houses kept the order of trades when sundials became useless on cloudy days.

Lamport 1978 · Fidge 1988 · Mattern 1988

Many Copies, Acting as One

When data is held in several copies, what does it take for them to act as one? And who could ever tell the difference?

We find out by exploring how three ancient Greek trading houses filled one another's orders in the sequence they really came, though none of them could read the hour.

Herlihy & Wing 1990

Taking Stock Without Stopping

How do you take stock of a whole system that never stops moving, when no one can see all of it at once? And what can such a count reliably tell you?

We find out by exploring how ancient Greek trading houses, hearing that bandits were taking their carts, counted every jar they owned, including those in transit, without interrupting ongoing trades.

Chandy & Lamport 1985

Arche · The Foot of Mount Phyle

Consensus & Crash Faults

Read this first

The Setting: The Foot of Mount Phyle

The hill, the four camps and the ravens between them, which every book here takes for granted. After it, the books below can be read in any order.

The Limits of Agreement

Can machines always agree when one of them may stop silently and messages take any time at all?

We find out by exploring how four mercenaries at the foot of a hill, unable to see one another, tried to agree whether to attack or hold when any of them might be dead.

Fischer, Lynch & Paterson 1985

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.

Dwork, Lynch & Stockmeyer 1988

Answering While Cut Off

When one part of a system is cut off from the rest, should it keep answering and risk being wrong, or stay silent until it can be sure? Can it ever have both?

We find out by exploring what the same Greek mercenaries could promise one another about their standing plan when ravens were lost and one tent was cut off.

Brewer 2000 · Gilbert & Lynch 2002

Agreeing by Chance

If no plan can guarantee agreement when a machine may stop without warning, can chance succeed where planning cannot? What if a machine that is stuck simply tosses a coin?

We find out by exploring how Greek mercenary camps, deadlocked over a plan, let a coin, tossed by each man alone in his tent, break the tie.

Ben-Or 1983

Telling the Dead from the Slow

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.

Chandra & Toueg 1996

Arche · The Crown of Mount Phyle

Byzantine Faults & Replication

Read this first

The Setting: The Crown of Mount Phyle

The hill, the crown, its four posts and the ravens between them, which every book here takes for granted. After it, the books below can be read in any order.

Agreeing Among Liars

Can machines agree when some of them may lie, telling one thing to one and something else to another? How many honest machines does each liar cost?

We find out by exploring how four bandits holding a hilltop, some of whom might lie, agreed whether to hold it or scatter, first by plain word and then under seal.

Lamport, Shostak & Pease 1982 · Pease, Shostak & Lamport 1980

Keeping Order Among Liars

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.

Castro & Liskov 1999

Changing Leaders Among Liars

When some machines may lie, replacing a leader has been slow and costly. Can a new leader take over as cheaply as any ordinary step, and at the pace of the messages rather than of a timer?

We find out by exploring how four bandits holding a hilltop took turns keeping their loot scroll, each gathering the others' seals into one bundle instead of every man writing to every other.

Yin, Malkhi, Reiter, Gueta & Abraham 2019

Paxos · The Scholars' Coast

Replication Without Assembly

Read this first

The Setting: The Scholars' Coast

The libraries, the couriers and the words every book there uses, which every book here takes for granted. After it, the books below can be read in any order.

Spreading by Word of Mouth

Can an update reach every machine in a large system just by each passing it on to a few others, with no one organising the spread?

We find out by exploring how news spread among the scholars of Paxos by word of mouth, and how they caught whatever the gossip missed.

Demers et al. 1987

Probably Up to Date

When a store reads from only some of its copies, how likely is an answer to be out of date, and by how much? Can we promise that it is probably not?

We find out by exploring how ancient Greek libraries, each consulting only a few of the others, judged how likely a copy was to be out of date.

Bailis et al. 2012

Changes That Never Clash

Can some changes be combined in any order, any number of times, and still come out the same everywhere, so that they never clash and no one ever needs to coordinate?

We find out by exploring how Greek scholars far apart kept a shared count that always came out the same, without ever meeting to settle it.

Shapiro, Preguiça, Baquero & Zawirski 2011 · the same authors' comprehensive study, 2011

What You Can Promise Alone

When a machine cannot stop to check with the others on every change, what can it still promise on its own? That no one sees a reply before the message it answers? That no one sees a change half made? That two people never take the last item?

We find out by exploring what ancient Greek librarians could still promise their readers when the couriers between the libraries stopped running.

Bailis et al. 2014

Paxos · The Hall of Two Doors

When Coordination Is Needed

Read this first

The Setting: The Hall of Two Doors

The hall at the fork and the two kinds of question, which every book here takes for granted. After it, the books below can be read in any order.

Knowing When to Wait

Which problems can machines solve without ever waiting for one another, and which force them to wait?

We find out by exploring how the scholars of Paxos told the questions they could settle alone from those that needed an assembly.

Hellerstein 2010 · Ameloot, Neven & Van den Bussche 2011