← The Books

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.

After Eric A. Brewer, Towards Robust Distributed Systems, 2000 · Seth Gilbert and Nancy Lynch, Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services, 2002

On a calm, overcast day a mercenary sits at the mouth of his linen tent on a headland above the sea, a basket of ravens beside him, looking up at a single hawk circling in the empty sky
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

Many copies, one service

A service stores copies of its data on several machines, and clients may read or write at any of them.

Three things are wanted of such a service. Every read should see the latest completed write, as if there were one copy. Every request to a working machine should be answered. And both should hold although the network may lose messages, even every message between two groups of machines.

  • Brewer (2000) conjectured, and Gilbert and Lynch (2002) proved: no service can have all three. When the network splits, a part must refuse some requests or answer from a copy that may be stale.
  • Gilbert and Lynch (2012): this is one case of a wider fact. A promise that nothing goes wrong and a promise that something happens cannot always both be kept.

So the choice comes when the network splits, and what is left to settle is which wish to give up and for how long. We tell it with four mercenaries, their ravens, and a plan they share between them.

A write, then a read, with the link cut

MACHINE A
1
link cut ✗
MACHINE B
1

A lone linen tent with a round shield, a chest and a basket on a rocky slope below a ring wall on the summit, with cypresses and pines around it
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.* Bandits hold the top of the hill, and the four must all attack or all hold. The tents cannot see one another, so word passes between them only by raven.

A known flightNo wind blows on these nights, so a raven that arrives does so within a time that all four know.
A hawk may take any birdA hawk may take a raven in the folds of the hill. Nobody sees it taken, and the bird never arrives.
Nobody stops, nobody commitsOn these nights no man stops, no man lies, and nothing is decided. The four only share a plan and answer one another about it.
A plan to follow

The standing plan

Until they commit, the four have a standing plan: the answer they mean to commit to, as things stand. At dusk it is hold.

Any man who sees something on their side of the hill may move the plan to the other answer, and any man may ask which plan stands. Each tent has its own note of it. A move is done when the man who made it is told it stands, and a question is done when the man who asked is told attack or hold. Nobody commits in this book, and nothing follows from which plan stands. What matters here is only what each man is told.

These nights differ from the others at the camps in one thing: a raven can be lost. A hawk may take it in the folds, and it never arrives. Nobody sees a bird taken, so a man waiting on a bird learns it was lost only when longer than any flight has passed and it has not come, and even then learns nothing of what it carried. On some nights every bird between one tent and the other three is lost, for as long as the hawks keep to that fold. That tent is cut off.

Send a bird below with no hawks about, and it lands within a flight. Then bring the hawks to tent 4's fold, send a bird from tent 2 to tent 4, and let a flight pass. Number 4 learns that a bird was lost, and nothing more.

Ravens and hawks send a bird and see what comes

The hill from above. A raven is a dot flying round the hill between two tents. While hawks are in the fold of tent 4, every bird to or from tent 4 is lost.

Send a bird, and see whether it comes.

On the night this book is about, tent 4 is cut off. Number 4 is alive and well and in the tent, wants to know which plan stands, and wants to know now. Something has to be said to Number 4, and the four have not yet settled what they owe a man who asks.

Two debts, and a condition

What the four owe each other

What the four owe a man who asks comes to two debts, and both must be paid while birds can be lost.

The first debt is about what an answer says, and the second is about getting an answer at all. The condition is the hawks.

First debt

Answering as one

Each tent has its own note, but the plan behaves as one plan. Every move and every question, at all four tents, fits one order in which a single record would have given every answer, each taking effect at a moment between its start and its answer, and anything finished before another began coming first.* If Number 2 has moved the plan to attack and been told it stands, a man who asks afterwards must hear attack, or a later move.

Second debt

Every man is answered

A man who asks, or moves the plan, is answered in the end, from what their tent holds. No limit is set on how soon, only that the answer come.

The condition

Birds may be lost

A hawk may take any bird, on any night. The two debts must be paid all the same.

Two ways of answering look safe, and each leaves one debt unpaid. Suppose Number 2 has moved the plan to attack and been told it stands, and Number 3 asks afterwards. A tent that says hold to every question has answered, but wrongly whenever attack stands. A tent that waits until the hawks leave has said nothing wrong and has not answered either, since the hawks may stay all night. Try both below.

Two ways to answer badly Number 3 asks

Number 2 has moved the plan to attack and been told it stands. Later Number 3 asks which plan stands.

The four have two things in their favour on these nights. Each tent has a sandglass. The glasses run alike, so a man can measure how long they have waited, though no man can tell what another's glass shows. And no wind blows, so a bird that arrives does so within a known flight. That is the calm of a windy night once the wind has dropped,* and here it holds from the start. The wind comes back at the end of the book.

That makes three things to promise together: answering as one, answering every man, and doing both while birds can be lost. Whether the four can promise all three is still open.

Close up of a tent's sandglass standing on the lid of an iron-bound wooden chest: two glass bulbs between turned wooden posts, the sand half run through, with limestone and the edge of a linen tent soft behind
The camps of this book, stated formally
  1. On these nights there is no wind. A bird that arrives does so within a known time, a flight; a man answers a bird within a known time of that man's own.
  2. Any bird may be lost, and between a cut-off tent and the rest every bird is lost, for as long as that lasts.
  3. Each tent has a sandglass. The glasses run alike, so a man can measure the length of a wait, but no man can tell what another's glass shows.

Gilbert & Lynch's partially synchronous model with arbitrary message loss, §4.1: a known bound tmsg on delivery of messages that are not lost, and local timers at the same rate.

The first result

The cut-off tent

The four cannot promise all three. Of answering as one, answering every man, and carrying on while birds can be lost, they may have any two. The impossibility was first put as a claim, and only later proved.

The Cut-Off Tent. When birds can be lost, no arrangement of the four can both answer every man and answer as one, even with a known flight and glasses in every tent.

The proof takes two nights that begin alike, with the plan at hold and tent 4 cut off. On the first Number 2 moves the plan, and on the second nobody does. Scroll through them, and watch what Number 4 has to go on each night: the note in the tent, the glass, and whatever birds have come in.

1 · Dusk

Tent 4 is cut off

The plan stands at hold. Every bird between tent 4 and the other three will be lost, for as long as this lasts.

2 · The first night

Number 2 moves the plan

Number 2 moves the plan to attack. Every man is answered, so Number 2 is told it stands. Whatever birds go to tent 4 are lost. Nothing else happens anywhere.

3 · The second night

Nobody moves the plan

The same dusk, and nothing happens anywhere for at least as long as the first night's move took. Then Number 4 asks which plan stands, and is answered. Nobody moved it, so a single record says hold.

4 · Put together

Both nights at once

Let the first night happen among the three and the second at tent 4. Nothing reaches tent 4 in either. Number 4 has the same note, the same glass and no bird, and asks after Number 2's move was finished.

5 · So

Number 4 says hold

Number 4 cannot tell this from the second night, so says what was said there: hold. But Number 2's move was finished before Number 4 asked, and a single record would say attack. The arrangement does not answer as one.

Number 4 did not answer badly. Everything on Number 4's side of the lost birds is the same on both nights, so Number 4 must give the same answer on both. On the second night hold is exactly right. The two nights want different answers, and the answer that is right on the second breaks answering as one on the first.

A known flight and glasses that run alike were both given to the four in the proof, and neither helped. What Number 4 lacks is news, and no amount of waiting brings a lost bird. Nor does the proof need tent 4 to be alone. With any division of the four into two sides the argument is the same.

So the four cannot have all three. Which two they may keep, and by what arrangement, is the next thing to settle.

Proof · that no arrangement both answers every man and answers as one

In the paper's terms the tents are nodes, a lost bird is a lost message, a cut-off tent is a partition, answering every man is availability, and answering as one is atomic consistency. Theorem 2. In the partially synchronous model, with a known bound on delivery of messages that are not lost and local timers at the same rate, no algorithm guarantees both availability and atomic consistency in all executions, including those in which messages are lost. The two nights are the paper's executions α₁ and α′₂, put together they are its α, and T below is a time measured by the glass.

  1. Suppose some arrangement did both. Put tent 4 on one side and the other three on the other, and lose every bird between them for the whole of what follows.
  2. The first night. The plan stands at hold. Number 2 moves it to attack. Since every man is answered, Number 2 is told it stands. Nothing else happens anywhere. Call the time this takes T, by the glass.
  3. The second night. The plan stands at hold. Nothing happens anywhere for at least T. Then Number 4 asks which plan stands, and is answered. Nobody moved it, so answering as one gives hold.
  4. Put them together. Let the first night happen among the three and the second at tent 4, at the same time. The three cannot tell this from the first night, since nothing reaches them from tent 4 in either, so Number 2's move is made and answered as before. Because of the quiet time, Number 4 asks after Number 2's move was finished.
  5. Number 4 cannot tell this from the second night. Number 4 began with the same note, the glass has run the same, and no bird has reached tent 4 in either. So Number 4 answers hold.
  6. But Number 2's move was finished before Number 4 asked, so it comes first in any order that answers as one, and a single record would have said attack. That contradicts the supposition.∎
Any two of the three

The muster-master's arrangement

The four cannot have all three, but they can have any two, and one arrangement gets them most of the way. It gives one tent a single job: to be the muster-master, the only tent whose note of the standing plan counts.

Why the four need one. When every tent has its own note, the notes can drift apart. Number 2 moves the plan to attack, and for a while only tent 2's note says so. A man who asks at tent 3 in that while reads hold from a note that is out of date, and nothing in the camp is wrong except that two notes disagree. Answering as one asks that every answer be what a single record would say, and with four records there is no single record to say it. The surest cure is to have only one.

What the muster-master is. Say it is tent 1. The muster-master is no wiser or higher than the others, and Number 1 is a man like the rest, with no vote and no say in the plan. The muster-master is a role, and the whole of it is to hold the one note that settles what the plan is. The notes at the other three tents are no longer the plan. At most they are what the muster-master last sent there, to read back, and a man never answers from them alone.

What the muster-master does. A man at any other tent who moves the plan sends a bird to tent 1 and waits. Number 1 changes the note and sends a bird back saying it stands, and only then is the man told it stands. A man who asks does the same: the bird goes to tent 1, Number 1 reads the note and sends back what it says, and the man is told that. Say Number 2 moves the plan to attack and is told it stands. When Number 4 asks afterwards, the bird to tent 1 finds the note at attack, and attack is what comes back. A man at tent 1 has no bird to send and is answered on the spot.

Why one order comes of it. The muster-master deals with birds one at a time, in the order it takes them in. Every move and every question therefore falls into one order, the same whichever tent it came from, and each answer is read from the one note as it stood at that point in the order. Two birds that reach tent 1 together may be dealt with either way round, since the men who sent them were each still waiting and neither was finished before the other began. Where one man's business was finished before another's began, its bird was dealt with first. That is what answering as one asks for, and it holds with no hawks and with hawks alike.

What it costs. Every man but Number 1 is answered only when a bird has gone to tent 1 and come back. While the birds fly, every man is answered. When the hawks take a bird, the man who sent it hears nothing, because nothing in his own tent can answer for the muster-master. A tent cut off from tent 1 falls silent, and if tent 1 is the one cut off, the other three do. Answering as one stays whole, since every answer that is given is the muster-master's. What is given up, on the nights and at the tents the hawks cut off, is answering every man. The muster-master's arrangement pays the first debt in full and the second only as far as the birds allow.

The other pairings of the three have their arrangements as well.

Answering as one, while birds can be lost

The muster-master's arrangement

When tent 4 is cut off, Number 4's bird does not arrive and Number 4 is not answered, so the tent in effect falls silent. Every answer that is given is right. When no bird is lost, every man is answered.

Answering as one and every man, while no bird is lost

The same arrangement

This pair asks for nothing new. With no bird lost, every bird reaches the muster-master and every answer comes back.

Answering every man, while birds can be lost

Each from their own note

Let each man answer from their own note, whatever it says. Every man is answered at once, and answering as one is given up. In the worst case a man who has heard nothing since dusk says hold all night.

The three nights below put the same business to each arrangement: Number 2 moves the plan to attack, and Number 4 asks later. Choose a night and watch which of the three things is kept, and which is given up or goes untested.

Three nights Number 2 moves the plan to attack; Number 4 asks later

Choose a night.

Each of these choices is made once and followed every night. A camp that answers from its own notes can be wrong on a night when every bird arrives. Most nights no fold has hawks in it, and the four would be giving up answering as one on all of them because birds may be lost on some.

The muster-master's arrangement, stated formally
  1. One tent has the only note of the standing plan.
  2. A man at any other tent is answered only when the muster-master's answer has come back.
  3. The muster-master deals with birds one at a time, in the order they are taken in.

The centralized algorithm, §3.2.1–3.2.2.

Proof · that the muster-master's arrangement answers as one

In the paper's terms the muster-master is the designated node of the centralized algorithm, and answering as one is atomic consistency. Claim. Ordering all moves and questions by the moment the muster-master dealt with them, every answer is what a single record would say, each takes effect between its start and its answer, and anything finished before another began comes first.

  1. Order all moves and questions by the moment the muster-master dealt with them. This is one order, the same whichever tent the man was at.
  2. Every answer is the muster-master's, from the muster-master's one note in that order, so each is what a single record would say.
  3. The muster-master deals with a man's business after it began, since the bird was sent then, and before it ends, since the answer waits for the muster-master. So each takes effect between its start and its answer, and anything finished before another began was dealt with first.∎
A glass to wait

Waiting a glass

The four need not give up answering as one on every night. On a night with no hawks the muster-master's arrangement already gives answering as one and an answer for every man.

What the four want is to lose answering as one only while birds are actually being lost, and to answer every man throughout. They can, because a bird that arrives does so within a known flight. A man who has waited two flights and the muster-master's time to answer, and has heard nothing, knows that a bird was lost and can stop waiting. Three rules make use of that.

First

Start a glass

A man who moves the plan or asks sends a bird to the muster-master and starts a glass that runs for two flights and the muster-master's time to answer.

Second

The answer comes in time

If the muster-master's answer comes before the glass runs out, the man takes it.

Third

The glass runs out first

The man answers from their own note. A question gets the latest plan the muster-master has sent them, unless they have themselves moved the plan since, and then it gets their own move. A move is told it stands.

Earlier on the night below Number 2 moved the plan to attack, and tent 4's note still says hold. Bring the hawks to tent 4's fold and let Number 4 ask or move the plan, and watch the glass run out. With no hawks about, the muster-master's answer comes before it does.

The glass earlier tonight Number 2 moved the plan to attack

Number 4's glass

Waiting a glass works for a plain reason. When no bird is lost, no glass runs out, and the arrangement is the muster-master's, which answers as one. When a bird is lost, the glass runs out and the man answers anyway, so every man is always answered. On any night on which no bird is lost, then, every answer is as one.

The Cut-Off Tent still stands. On its first night Number 4's glass runs out and Number 4 says hold, as that result says any arrangement answering every man must. What waiting a glass buys is that this happens only on nights when birds are actually lost.

Waiting a glass buys nothing after a loss. If Number 4 moved the plan while cut off, the muster-master never heard of it, and nothing here tells the muster-master. Long after the hawks have gone, the others are told a plan Number 4 has moved away from. The picture shows it: move the plan from tent 4 under the hawks, send the hawks away, and let Number 2 ask. The promise covers whole nights on which no bird is lost, and says nothing about the glasses that follow a loss.

The hawks may have left long ago, and a man's note may still be hours behind. What the four lack is a promise that the damage ends.

Waiting a glass, stated formally
  1. A man who moves the plan or asks sends a bird to the muster-master and starts a glass that runs for two flights and the muster-master's time to answer.
  2. If the muster-master's answer comes before the glass runs out, the man takes it.
  3. If the glass runs out first, the man answers from the tent's own note: a question gets the latest plan the muster-master has sent that tent, unless the man has moved the plan since, in which case it gets that move; a move is told it stands.

A timeout of 2tmsg + tlocal, §4.3.

The damage ends

How stale, and for how long

The four can promise the damage ends, and the promise has a span of time in it, fixed in advance and measured by the glass. A loss does its damage only while it lasts and for the span after. Nobody can promise how long the hawks stay. The four promise only how long they take to catch up.

Catching up means that a move made without the muster-master reaches the muster-master, and then every tent. At the camps birds come in any order, so a man cannot count on an earlier bird arriving first. Every bird a man sends the muster-master therefore carries, before anything else, all the moves that man has made that the muster-master has not yet acknowledged, in the order they were made. The muster-master stamps each move as it comes in, and every bird from the muster-master carries the plan and its stamp, so that a man can go by the plan with the highest stamp to have come. Scroll to watch a move that Number 4 made while cut off find its way round.

1 · Cut off

Number 4 moves the plan

Hawks are in the fold of tent 4. Number 4 moves the plan to attack and sends the move to the muster-master. The bird is lost. After a glass Number 4 is told it stands.

2 · Sent again

Until acknowledged, send it again

Number 4 sends the move again and again, often enough that with no bird lost it would reach the muster-master within half the span. Each bird is lost while the hawks stay.

3 · The hawks leave

One bird gets through

The next bird after the hawks leave reaches the muster-master. The muster-master changes the note and gives the move the next stamp.

4 · The muster-master sends it round

Every tent learns the plan

The muster-master sends the plan and its stamp to every tent, again to any that has not acknowledged it, often enough that with no bird lost they arrive within half the span.

5 · A span

No bird is lost for a span

From the moment the hawks left, a span longer than the promised one passes with no bird lost. Everything the loss did is now mended.

6 · A question

Anyone asking now hears attack

A question begun after that span is answered with Number 4's move or a later one. Here Number 3 asks, and is told attack.

The Span. The muster-master's arrangement with a span answers every man, answers as one on any night on which no bird is lost, and on every night keeps the promise of the span. The damage lasts only as long as the loss and a span after.

The picture leaves one thing out. All through the loss, the three went on moving and asking through the muster-master. Take Number 2 moving the plan to hold while Number 4, cut off, moves it to attack. The muster-master stamps both once Number 4's bird arrives, and the plan ends at whichever move was stamped later, so the promise is kept. For a while, though, two men are each told a different plan stands, and no promise about when they learn of it undoes that. Step through it below.

Two men move the plan the plan stood at attack, stamp 1

Every part of this leaned on a known flight: the glass that runs out, the birds sent again often enough, and the span itself. A windy night has no known flight, and what is left of the promise then has still to be seen.

The promise of the span, stated formally

All the moves and questions can be set in one order P, with t the span, fixed in advance and measured by the glass, in which:

  1. all moves are ordered among themselves, and every question is placed relative to every move;
  2. every question is answered with the plan of the last move before it in P, or hold if there is none;
  3. each man's own business keeps its order in P;
  4. if no bird was ever lost, P answers as one;
  5. and whatever happens, if something was finished, and then a span longer than t passed with no bird lost, and only then something else began, the first comes before the second.

Delayed-t consistency, Definition 3.

The muster-master's arrangement with a span, stated formally

At every tent, always: every bird from the muster-master carries the plan and its stamp, and a man goes by the one with the highest stamp to have come. Every bird a man sends the muster-master carries all that man's unacknowledged moves, in order.

A question: send to the muster-master and wait a glass. If the muster-master answers in time, give that answer. If not, give the latest of the asker's own unacknowledged moves, or if there is none, the plan with the highest stamp the asker holds.

A move: send to the muster-master and wait a glass. It stands when the muster-master acknowledges it or the glass runs out, whichever is first. Until acknowledged, send it again, often enough that with no bird lost it reaches the muster-master within half of t.

At the muster-master: each move that reaches the muster-master, taken in its sender's order, changes the muster-master's note and takes the next stamp. The muster-master sends the plan and stamp to every tent, again and again to any that has not acknowledged it, often enough that with no bird lost they arrive within half of t.

The modified centralized algorithm, Theorem 4.

Proof · that the muster-master's arrangement with a span keeps the promise

In the paper's terms (Definition 3 and Theorem 4), t is the span, fixed in advance and measured by the local timers, and P is an order on all the moves and questions of a night. Claim. On every night the muster-master's arrangement with a span answers every man, and admits an order P satisfying clauses (1) to (5) of the promise of the span, stated above.

  1. The order. Order the moves by the muster-master's stamps; a move that never reaches the muster-master goes after all the stamped ones, in the order it was made. Place each question immediately after the move whose plan it was given, or at the start if it was given hold from dusk. Then every question is answered with the last move before it: clauses (1) and (2).
  2. Each man's own order. A man's moves reach the muster-master in the order they were made, since each bird carries all the earlier unacknowledged ones first; so the muster-master stamps them in that order, and has stamped them before answering that man's question. A man never answers with a lower stamp than one already held, and that man's own unacknowledged moves are newer than anything the muster-master has sent. So each man's questions land after that man's earlier business: clause (3).
  3. No bird lost. Then no glass runs out, every answer is the muster-master's, and this is the plain muster-master's arrangement, which answers as one: clause (4).
  4. A move, then a span. Suppose a move by Number 4 was finished, then more than t passed with no bird lost. In that span the move reaches the muster-master and the muster-master's stamp for it reaches every tent, each within half of t. So any move begun after the span gets a higher stamp, and any question begun after it is answered with this move or a later one.
  5. A question, then a span. The plan a finished question was given came from the muster-master or from a move of the asker's own. Either way, within the span that move is stamped and sent to every tent, and the last step places everything begun after the span later in P: clause (5).∎

The paper's own proof of this is a few lines long, and says nothing about how a man should treat moves of that man's own that the muster-master has not yet acknowledged; the second step supplies it.

Everything leaned on a known flight

When the flight has no bound

A known flight is what a wind takes away, and waiting a glass does not survive it. A glass that runs out means a bird was lost only because there is a known flight.

On a windy night there is none. A bird may sit in the pines for any time, and a man who has waited any length of time cannot tell a lost bird from a slow one.* Then something stronger is true.

The Wind. If flights have no bound, no arrangement that answers every man can answer as one even on the nights when no bird is lost.

Mount Phyle from the air: a steep wooded crag with a ruined wall on top, pines on the slopes, small white tents among them and the sea beyond

The two windy nights below look the same from tent 4. On one a hawk takes Number 4's bird, and on the other the bird sits out the wind in a pine. Let Number 4 ask and wait, have Number 4 answer, and then let the night go on.

Two windy nights seen from tent 4

One night

Suppose a hawk takes the bird.

Another night

Suppose the bird sits out the wind in a pine.

Number 2 has moved the plan to attack and been told it stands. Number 4 now asks which plan stands.

On the second night no bird was lost, and the wrong answer was given all the same. Number 4 had to answer before the slow bird landed, and could not tell that night from the first. So in a wind an arrangement that answers every man can be wrong even on a night when every bird arrives. The results go no further than this, and it is worth marking where they stop.

Proof · that in a wind, answering as one cannot even be promised when nothing is lost

In the paper's terms a night is an execution, and in the asynchronous model there is no bound on message delay. Corollary 1.1. No algorithm that guarantees availability in every execution guarantees atomic consistency in every execution in which no message is lost.

  1. Suppose an arrangement answers every man on every night, and answers as one on every night on which no bird is lost.
  2. By the Cut-Off Tent, which holds in a wind as well, there is a night on which a bird is lost and a wrong answer is given. It is given after only so much has happened.
  3. Take that night up to the wrong answer. Let every bird that was lost instead be still in the pines, arriving afterwards; in a wind nobody can tell the difference. Continue the night so that every bird arrives.
  4. On this night no bird is lost, and up to the wrong answer it is the same night, so the wrong answer is still given. That contradicts the supposition.∎
Four questions

What being cut off does not say

The Cut-Off Tent is easily taken for more than it says. Four questions mark where it stops.

Is this the camps' impossibility?

The camps' impossibility is a different result. With one man who may fall silent and no longest flight, the four cannot be sure of ever committing.* That has the same shape as the Cut-Off Tent: something that must never go wrong, and something that must in the end happen, which cannot both be promised. But neither result gives the other. There, no bird is lost and one man may stop. Here, no man stops and birds are lost instead.

Is it about a dead man?

The result is about a living man. A man who has stopped owes no one an answer. Number 4 is alive and wants to know, and that is why the question has to be put to tent 4 at all.

Does it cover everything the four know?

A thing that needs no news is outside the result. Which number each tent bears never changes, and any man, cut off or not, can say so and be right. The result is about a plan that can be moved, where one tent needs news of the others.

Must the four choose once for all?

The four need not choose once for all. They may answer as one for the standing plan and answer at once for something that matters less, or answer questions from their own notes while moves wait for the muster-master. Each such division gives up a little of both, and each is still bound by the Cut-Off Tent wherever a man answers from a note that may be behind.

Back to machines

The camp was a service of copies

Read the foot of the hill again with machines in the tents. Every tent is a machine holding a copy of the data, every raven is a message, and a cut-off tent is a part of the network that no message reaches or leaves. Hover over a row, or tap it, to see who is who.

At the foot of the hill
In the machine room

A service cannot be consistent, available and partition-tolerant at once.

Since networks do partition, the real choice comes when one does: refuse some requests to keep every answer consistent, or answer every request and let the copies diverge.

This is one case of a wider fact: a safety property and a liveness property often cannot both be guaranteed. Real systems divide the trade-off by data or by operation.

The Foot of Mount Phyle, in detail All the papers

Setting The Foot of Mount Phyle

The papers behind this book

Eric A. Brewer, Towards Robust Distributed Systems. Invited talk, 19th ACM Symposium on Principles of Distributed Computing (PODC), Portland, Oregon, July 2000. — The conjecture: of consistency, availability and tolerance to network partitions, a shared-data system can have at most two; the three cases and their examples.

Seth Gilbert and Nancy Lynch, Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. ACM SIGACT News 33, 2 (June 2002), 51–59. — The formal model, the impossibility in the asynchronous and partially synchronous models (Theorems 1 and 2, Corollary 1.1), the centralized algorithm, and Delayed-t consistency (Theorem 4).

Seth Gilbert and Nancy Lynch, Perspectives on the CAP Theorem. IEEE Computer 45, 2 (February 2012), 30–36. — CAP as a trade-off between safety and liveness, its relation to FLP, and the ways real systems divide the trade-off.

The ideas, plainly. In 2000 Eric Brewer conjectured that a shared-data system can have at most two of three properties: consistency, availability, and tolerance of network partitions. Gilbert and Lynch made the conjecture precise and proved it. Consistency is atomicity, or linearizability: the system behaves as if there were one copy of the data. Availability means every request received by a working node eventually gets a response. Partition tolerance means these hold even though the network may lose any messages, including every message between two groups of nodes.

The proof is a single indistinguishability argument. Cut the nodes into two groups and lose every message between them. A write completes in one group; later, a read arrives in the other. That group cannot tell this execution from one with no write, so if it answers at all, it is wrong. Timers and a known delivery bound do not help, because the missing information cannot arrive.

Any two of the three can be had. A single designated node gives consistency always and availability whenever there is no partition. With timers and a delivery bound, a node can time out and answer locally only when messages are actually lost, and Delayed-t consistency bounds how long stale answers persist once the partition heals. Without a delivery bound, even that is impossible.

CAP is one case of a wider fact about unreliable systems: a safety property and a liveness property often cannot both be guaranteed. Real systems divide the trade-off by data or by operation.