Consistency Models, CAP and PACELC: What a Cut-Off Node Actually Does

One etcd node cut off from its cluster, measured. During the cut its linearizable reads and writes got no answer, and its serializable reads all answered out of date. Plus what CAP proves, what “2 of 3” gets wrong, and what consistency costs day to day.

“Consistent” is one of the most overloaded words in computing. A database vendor, a textbook and a job interviewer can each mean something different by it, and none of them will say which.

This part pins it down by watching a real system make the choice. A three-node etcd cluster keeps taking writes while one of its nodes is cut off. We ask that node for data, two different ways, and record every answer. Then we measure what consistency costs when nothing is broken at all.

Try this first

Three database nodes hold copies of the same counter. A writer is incrementing it through two of them. The third node loses its connection to the other two, but your client can still reach it.

Your client asks the cut-off node for the counter. What should it do?

1. Refuse to answer.
2. Answer with the last value it knows, which may be out of date.
3. Answer with the current value.

Write down your answer. Then look at what etcd did, below. The answer depends on a single flag in the request.

One node, two answers

The lab cut one follower off from the other two for ten seconds, while a writer kept writing through the majority. The cut drops every packet between that node and its peers, as a failed network would; the node can’t tell a cut from silence. Four kinds of request kept arriving during the cut:

Request	Answered correctly	Answered, but out of date	No answer
Cut-off node, linearizable read	0 of 3	0	3 of 3
Cut-off node, serializable read	0 of 194	194 of 194	0
Cut-off node, write	0 of 4	—	4 of 4
Majority node, linearizable read	190 of 190	0	0

Meanwhile the writer carried on: 438 writes succeeded during the cut, all through the majority side.

Option 3 was never on the table. The cut-off node can’t know the current value, because the writes are happening somewhere it can’t hear. So it has two choices left, and etcd lets the client pick.

• A linearizable read asks the node to confirm with the cluster that it’s up to date before answering. The rest of the cluster is unreachable, so the node waits. None of the three reads that began during the cut got an answer before the lab’s 3-second limit. Writes to the cut-off node got nothing back either.
• A serializable read asks the node to answer from what it has. Every read got an answer, and every one was out of date. The value it returned was the one it held when it was cut off, which by the end of the cut had been out of date for 10 seconds.
• The majority side carried on normally. Two of three nodes can still agree, so linearizable reads there were answered and fresh every time.

The lab ran this three times on fresh clusters, and the rows above were the same in every run to within one operation.

etcd’s documentation describes the two modes in its own words: “etcd ensures linearizability for all other operations by default. Linearizability comes with a cost, however, because linearized requests must go through the Raft consensus process.” A serializable read “may access stale data with respect to quorum, but removes the performance penalty of linearized accesses’ reliance on live consensus.”

That’s CAP, observed on reads and writes. During a partition, a node that can’t reach the majority can refuse to answer or answer out of date. It can’t do what you’d want, which is answer correctly.

How each answer was judged

“Out of date” here is a checked claim, not a guess. The lab logged every operation with when it started and when it finished. One writer wrote 1, 2, 3 and so on, in order. So a read is stale if it returns less than the last value whose write had finished before the read started, or less than a value some other read had already returned before it started. Linearizability forbids both. For a register with one writer that’s a sound test, though not a complete proof of linearizability. Operations that started while the lab was switching the cut on or off were left out of every count.

What CAP actually says

CAP began as Eric Brewer’s conjecture, and Seth Gilbert and Nancy Lynch proved a precise version of it in 2002. Their definitions are narrower than most people assume.

Consistency means linearizable, which they call atomic:

Under this consistency guarantee, there must exist a total order on all operations such that each operation looks as if it were completed at a single instant. This is equivalent to requiring requests of the distributed shared memory to act as if they were executing on a single node, responding to operations one at a time. One important property of an atomic read/write shared memory is that any read operation that begins after a write operation completes must return that value, or the result of a later write operation.

That last sentence is exactly the test the lab applied.

Availability means every request gets a response:

For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response.

Note what it doesn’t say. There’s no time limit. The authors call it weak for that reason, “it puts no bound on how long the algorithm may run before terminating”, and strong for another: “even when severe network failures occur, every request must terminate.” A system can be available in CAP’s sense and still take a minute to answer.

Partition tolerance isn’t a feature. It’s a description of the network: messages can be lost.

In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another.

And the theorem itself, for a network with no clocks:

Theorem 1 It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties: […] Availability […] Atomic consistency […] in all fair executions (including those in which messages are lost).

The authors restated it ten years later in one sentence: “In a network subject to communication failures, it is impossible for any web service to implement an atomic read/write shared memory that guarantees a response to every request.”

“Pick two of three” is wrong, and Brewer said so

The slogan came from Brewer himself. A 1999 paper with Armando Fox states a “Strong CAP Principle” as “Pick at most 2”, and his 2000 keynote slide says “at most two”. Twelve years later he wrote:

The “2 of 3” formulation was always misleading because it tended to oversimplify the tensions among properties.

And:

CAP prohibits only a tiny part of the design space: perfect availability and consistency in the presence of partitions, which are rare.

The problem with “pick two” is that it makes partitions sound optional. They aren’t. You can’t build a network that never loses a message, so you can’t choose to go without the P. Brewer’s 2012 paper puts it plainly: “If the choice is CA, and then there is a partition, the choice must revert to C or A.” What you actually choose is what happens when a partition occurs. In 2017, writing about Google’s Spanner, he still sorted systems into CA, CP and AP, but added: “you are not entitled to 2 of 3, and many systems have zero or one of the properties.”

The lab shows a second problem with the slogan. etcd didn’t make one choice for the whole system. It made a different choice for each request, based on one flag. Brewer again: “the choice between C and A can occur many times within the same system at very fine granularity”.

CAP’s C is not ACID’s C

The same letter means two unrelated things. In a database transaction (ACID), consistency means the data obeys its rules: unique keys, foreign keys, balances that add up. In CAP, it means linearizability of a single object. Brewer: “the C in CAP refers only to single-copy consistency, a strict subset of ACID consistency.” Part 19 covered the ACID kind.

What “unavailable” looked like

CAP’s availability has no time limit, so what does its absence look like in practice? The lab ran one more reader on the cut-off node: linearizable reads, with the client willing to wait up to 30 seconds.

In all three runs, that reader’s read was sent just as the cut went in. etcd didn’t answer it and didn’t refuse it. It held it for the whole ten seconds of the cut, and for another 2.4 to 2.5 seconds after the network was back, until, within one 50 ms poll, the node’s log started moving again: 12.8 to 12.9 seconds in all. Only then did it return an error, etcdserver: leader changed, which etcd’s source marks as one to retry (“return a retryable error.”). It never returned a value.

Every other linearizable read and write the lab sent to that node during the cut ended the same way: nothing came back, and the lab’s own 3-second limit ended the wait.

So the unavailable side of CAP, in practice, was mostly silence. That’s why Part 23 kept insisting on timeouts. Brewer makes the same point: “Operationally, the essence of CAP takes place during a timeout”. A client that waits forever has chosen consistency by default, whether it meant to or not.

After the partition heals

The cut ended, and the node’s serializable reads didn’t become correct at once. The lab polled its Raft log position every 50 ms. That position didn’t move at all during the cut. After the cut ended it stayed where it was for another 2.4 to 2.5 seconds across the three runs. Then, at the poll where it first moved, it had already reached the leader’s position.

So the stale answers after the heal weren’t the node slowly replaying a backlog: once its log moved at all, it was current. For those seconds its log hadn’t moved at all. The lab didn’t establish what took them. The lesson doesn’t depend on it: a node can go on serving old data for seconds after the network is fine again.

A serializable read is allowed to be stale at any time, including when nothing is wrong. It’s just rare when the node is healthy: the cut-off node’s serializable reads before the cut were all up to date.

A ladder of consistency models

Linearizability is one point on a scale. The weaker models allow more staleness, and in return keep working through more failures.

Model	What it promises	During a partition
Linearizable	Each operation appears to happen at one instant between its start and finish, in real-time order	Some nodes can’t answer
Sequential	Some single order that respects each client’s own order, not real time	Some nodes can’t answer
Causal	Operations that depend on each other are seen in that order by everyone	Works if each client sticks to one server
Read your writes	A client sees its own writes	Works if each client sticks to one server
Monotonic reads	A client never sees an older state after a newer one	Works everywhere
Eventual	If writes stop, replicas eventually agree	Works everywhere

The right-hand column follows Jepsen’s map of consistency models, which classifies them by how available they can be “for a distributed system on an asynchronous network”. Eventual consistency isn’t on that map; it’s here for comparison. And the lower rows aren’t a strict ladder: read your writes and monotonic reads are siblings, both implied by a model called PRAM, which Jepsen’s map puts above them. Read your writes is the one that needs a client to stick to one server. Part 20 measured read your writes on a real replica. Two of the definitions are worth reading in the original.

Herlihy and Wing on linearizability, 1990:

Linearizability provides the illusion that each operation applied by concurrent processes takes effect instantaneously at some point between its invocation and its response, implying that the meaning of a concurrent object’s operations can be given by pre- and post-conditions.

Lamport on sequential consistency, 1979:

the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program. A multiprocessor satisfying this condition will be called sequentially consistent.

The difference is real time. A sequentially consistent system may let you read something stale, as long as every client could agree on some order of events. Jepsen: “A process in a sequentially consistent system may be far ahead of, or behind, other processes. For instance, they may read arbitrarily stale state.”

“Eventually” has no deadline

Eventual consistency is the model people describe most loosely. Every definition in this part’s sources is conditional on writes stopping, and none gives a time limit. Werner Vogels’s, from 2008:

Eventual consistency. This is a specific form of weak consistency; the storage system guarantees that if no new updates are made to the object, eventually all accesses will return the last updated value. If no failures occur, the maximum size of the inconsistency window can be determined based on factors such as communication delays, the load on the system, and the number of replicas involved in the replication scheme.

Figures you’ll see, like DynamoDB’s replication “typically within a second or less”, are one vendor’s typical numbers, not part of the model. Gilbert and Lynch defined a separate, time-bounded model precisely because “we want an explicit time bound on how long it will take for the data to become consistent.”

Time going backwards

The lab had one more client: it made serializable reads, alternating between a majority node and the cut-off one.

Each read on its own was allowed. A serializable read may be stale. But to the client, the counter went 367, then 229, then 369, then 229. Time went backwards 236 times in that run. That breaks monotonic reads, one of the four session guarantees Douglas Terry and his colleagues defined in 1994:

Read Your Writes – read operations reflect previous writes. Monotonic Reads – successive reads reflect a non-decreasing set of writes. Writes Follow Reads – writes are propagated after reads on which they depend. Monotonic Writes – writes are propagated after writes that logically precede them.

This happens in real systems whenever a load balancer spreads one user’s reads over replicas that are at different points. A user refreshes a page and a comment they just saw disappears. The usual fixes are to keep a user on one replica, or to have the client remember the newest version it has seen and refuse to accept older ones. It’s a cheap guarantee to want: Jepsen notes that “Monotonic reads can be totally available”, meaning it can be kept even during a partition.

PACELC: the cost when nothing is broken

CAP only describes behaviour during a partition. Partitions are rare. Daniel Abadi pointed out in 2012 that the trade-off people live with every day is a different one:

A more complete portrayal of the space of potential consistency tradeoffs for DDBSs can be achieved by rewriting CAP as PACELC (pronounced “pass-elk”): if there is a partition (P), how does the system trade off availability and consistency (A and C); else (E), when the system is running normally in the absence of partitions, how does the system trade off latency (L) and consistency (C)?

The lab measured the “else”. It timed each kind of request with no partition, 400 of each, interleaved. First with the nodes as close as containers on one machine get, then with 20 ms of delay added to each node’s link to the others. The link between the client and the node it asked was left alone.

Request	Nodes close together	20 ms each way between nodes
Serializable read at a follower	1.16 ms	1.25 ms
Linearizable read at a follower	1.83 ms	82.69 ms
Serializable read at the leader	1.17 ms	1.36 ms
Linearizable read at the leader	1.53 ms	42.12 ms
Write at the leader	2.31 ms	42.83 ms
Write at a follower	2.65 ms	83.45 ms

Medians. Serializable reads didn’t care where the other nodes were: they answer from local data. Everything that has to agree with the cluster paid for the distance. A linearizable read at the leader cost about one round trip between nodes, two 20 ms hops. At a follower it cost about two. That fits how a Raft leader serves a linearizable read: it checks with a majority that it’s still the leader, and a follower has to ask the leader first. Writes cost the same, because a write has to reach a majority before it counts.

So that’s the “ELC” in PACELC, measured. On one machine it’s a millisecond or so and easy to ignore. Put the nodes in different cities and it’s the whole latency budget. That’s why so many systems offer the cheaper read, and some make it the default. etcd doesn’t: its default is linearizable.

Abadi classified the systems of 2012 by both halves. The default versions of Dynamo, Cassandra and Riak were PA/EL: available during a partition, low latency otherwise, and consistent in neither case. Fully transactional systems like VoltDB were PC/EC. His MongoDB example shows how slippery the labels are: he classified it PA/EC, while noting that “Technically, when a partition occurs, MongoDB is not available according to the CAP definition of availability”. And these were 2012 defaults: MongoDB’s default write concern has since changed to majority. Treat a system’s letters as a description of one configuration at one date, not of the product.

Quorums don’t give you linearizability

A common belief: if every write goes to W replicas and every read asks R replicas, and R + W is more than the number of replicas N, then every read overlaps every write and must see it. So quorums are consistent.

They overlap, but that isn’t the same thing. Abadi:

Technically, simply using a quorum protocol is not sufficient to guarantee consistency to the level defined by Gilbert and Lynch.

Three things break it in practice. Dynamo, the design most quorum systems copy, uses a “sloppy quorum”: writes go to “the first N healthy nodes from the preference list”, which may not be the replicas a later read asks. Abadi also notes that such systems typically set R + W ≤ N, although Dynamo’s own paper reports its common configuration as (3,2,2), where R + W > N. And conflicting writes are usually resolved by timestamp, last write wins. Jepsen tested a Cassandra-compatible database and found that with clocks just one second apart, updates were silently lost, and that “choosing consistency level QUORUM or ALL does nothing to prevent it”. Cassandra’s own documentation promises only that if quorums are used for both, “the write will be visible to the read”, and reserves the word linearizable for its Paxos-based lightweight transactions.

“Strong consistency” means whatever the vendor means

Martin Kleppmann, in a critique of CAP, puts it bluntly: “The term strong consistency is vague, and may refer to linearizability, sequential consistency or one-copy serializability.” Of the sources for this part, only Google’s Spanner documentation defines it precisely: “A replication protocol exhibits strong consistency if the replicated objects are linearizable.”

The vendors show why that matters:

• DynamoDB offers “strongly consistent” reads that return “the most up-to-date data”. In a multi-Region table in its default mode, a strongly consistent read “may return stale data if the item was last updated in a different Region.”
• CockroachDB answers its own FAQ question “How is CockroachDB strongly consistent?” with serializability, and its engineers’ blog says: “While Spanner provides linearizability, CockroachDB only goes as far as to claim serializability”. CockroachDB calls itself a CP system.
• etcd’s own documentation, in 2019, called sequential consistency “the strongest consistency guarantee available from distributed systems”. Jepsen: “This is incorrect: sequential consistency is strictly weaker than linearizability, and linearizability is definitely achievable in distributed systems.”

When a system promises “strong consistency”, ask which model. If nobody can tell you, assume the weakest one the words could mean.

Does Spanner beat CAP?

Google’s Spanner is often described as consistent and available, as if it had escaped the theorem. Brewer, by then Google’s VP of infrastructure, says no:

The purist answer is “no” because partitions can happen and in fact have happened at Google, and during (some) partitions, Spanner chooses C and forfeits A. It is technically a CP system.

It’s “effectively CA”, in his words, because Google’s private network makes partitions rare and availability is “better than 5 9s”. And the atomic clocks aren’t what do it: “TrueTime does not significantly help achieve CA”. TrueTime buys ordering, which is Part 25’s subject. It doesn’t buy immunity from partitions.

Asking for the consistency you need

Most systems offer more than one level, per request or per operation. Know the switch in the ones you use:

System	Cheaper, may be stale	Linearizable, or the strongest offered
etcd	serializable read	linearizable read (the default)
DynamoDB	eventually consistent read (the default), half the cost	ConsistentRead: true, within one Region
Cassandra	ONE, LOCAL_ONE	lightweight transactions (Paxos)
MongoDB	read concern local (the default); data “may be rolled back”	read concern linearizable with majority writes, primary only, one document
PostgreSQL	read from a hot standby, “eventually consistent with the primary”	read from the primary

Two of those deserve their small print. MongoDB tells you to “Always use maxTimeMS with linearizable read concern in case a majority of data bearing members are unavailable” which is the cut-off node’s silence again, with the vendor warning you about it. And PostgreSQL’s strongest standby setting, synchronous_commit = remote_apply, gives “causal consistency” only “In simple cases”, in its own documentation’s words. It never claims linearizable standby reads.

Explain it like I’m ten

Three friends keep a shared scorecard for a game, each holding a copy. Two of them sit together and keep updating the score. The third wanders off to the other side of the playground, out of earshot.

• Someone asks the third friend the score. They can say “I don’t know, I can’t hear the others”, or they can say what the score was when they left. They can’t say the real score, because they can’t hear it.
• Saying “I don’t know” is choosing to be right over being helpful. That’s consistency over availability.
• Saying the old score is choosing to be helpful over being right. That’s availability over consistency.
• Asking the two friends sitting together always gets the real score, because there are more of them and they can hear each other.
• Even when nobody wanders off, if you insist on the real score, the friend you ask has to check with the others first. That takes a moment. If they’re far apart, it takes longer. That’s PACELC’s else.

The precise version

• The scorecard is a replicated register. Wandering out of earshot is a network partition, and “the real score” is linearizability.
• “I don’t know” is the linearizable read that got no answer. The old score is the serializable read that answered stale.
• The two friends together are a majority quorum, which is why that side can still be both available and consistent.
• Checking with the others before answering is a ReadIndex-style confirmation. The time it takes is the latency cost of consistency.
• Where the analogy breaks: real systems don’t know they’ve been partitioned. A slow network and a cut one look the same until a timeout says otherwise.

Trade-offs

• Linearizable reads are correct and can go unanswered. Measured: none of the three that began during the cut answered within 3 s.
• Serializable reads always answer and can be stale. Measured: all 194 during the cut were stale, returning a value that was out of date by up to 10 seconds.
• Consistency costs round trips even without a partition. Measured with 20 ms between nodes: a linearizable read at a follower took 82.69 ms against 1.25 ms for a serializable one.
• Reading at the leader halves that cost. 42.12 ms against 82.69 ms, at the price of sending every correct read to one node.
• A majority keeps working. Measured: every linearizable read on the majority side answered correctly throughout the cut.
• Stickiness buys session guarantees. Keeping a client on one replica gives it monotonic reads and read-your-writes without paying for linearizability.

Common mistakes

• Saying “pick two of three”. Partitions aren’t optional. Brewer called the slogan “always misleading”.
• Calling a system CA without saying what it does when a partition comes. Brewer: “If the choice is CA, and then there is a partition, the choice must revert to C or A.”
• Confusing CAP’s C with ACID’s C. One is linearizability of an object, the other is a transaction preserving the database’s rules.
• Treating availability as fast. CAP’s availability has no time limit. The measured unavailable side went quiet: one read was held for nearly 13 seconds and then failed.
• Load-balancing reads across replicas without thinking about sessions. Measured: one client saw time go backwards 236 times in about 24 seconds.
• Assuming quorums are linearizable. Sloppy quorums, R + W ≤ N and last-write-wins all break it.
• Trusting the words “strong consistency”. DynamoDB’s “strongly consistent” read can be stale across Regions; etcd’s own docs once called sequential consistency the strongest.
• Assuming eventual means soon, or that healed means current. No definition bounds it, and the cut-off node went on returning stale reads for 2.4 to 2.5 seconds after the network recovered.

Interview questions

Try to answer each one before opening the model answer.

1. What does the CAP theorem actually say?

Show a strong answer

• Precisely: in a network that can lose messages, no read/write object can guarantee both linearizability and a response to every request received by a non-failing node.
• Consistency means linearizable, not ACID consistency. Availability means every request gets a response eventually, with no time limit. Partition tolerance means the network may drop messages.
• It constrains behaviour when messages can’t get through. When the network is fine, a system can be both, though Gilbert and Lynch note that on an asynchronous network, a message that’s merely slow is indistinguishable from a lost one.
• “Pick two of three” is wrong. Partitions happen whether you like it or not. You choose what the system does when one occurs, and you can choose differently per operation.

Likely follow-up: “So is CA possible?” Only on a network that never partitions, which doesn’t exist. Brewer: “If the choice is CA, and then there is a partition, the choice must revert to C or A.”

2. A replica is cut off from the leader, but a client can still reach it. What are its options?

Show a strong answer

• Refuse to answer, or wait: consistent but not available. Measured on etcd: linearizable reads and writes there got no answer within 3 s.
• Answer from its local copy: available but not consistent. Measured: serializable reads there all answered, and all 194 were stale.
• It can’t answer correctly, because the writes are happening where it can’t see them.
• The majority side is unaffected: it can still reach a quorum, so it stays available and consistent.

Likely follow-up: “How does the client tell the difference between ‘unavailable’ and ‘slow’?” It can’t, except by a timeout. That’s why every client needs one.

3. Explain linearizability versus sequential consistency.

Show a strong answer

• Both say operations appear in a single order.
• Linearizable adds real time: if one operation finishes before another starts, it must come first. A read that starts after a write finishes must see it.
• Sequential only requires each client’s own order to be kept. A client may read stale data as long as some global order explains everything.
• Example: you write x = 1 and tell a friend by phone; they read x and get 0. Sequential consistency allows that. Linearizability doesn’t.

Likely follow-up: “Why not always use linearizable?” It costs round trips: measured at 42 ms at the leader and 83 ms at a follower with 20 ms between nodes, against about 1.3 ms for a local read.

4. What is PACELC?

Show a strong answer

• Abadi’s extension of CAP: if there’s a Partition, choose Availability or Consistency; Else, choose Latency or Consistency.
• The “else” is the everyday trade-off. Partitions are rare; latency is always.
• Measured: with 20 ms between etcd nodes and no partition, linearizable reads took 42–83 ms and serializable reads about 1.3 ms.
• Examples from 2012: Dynamo-style systems were PA/EL; fully transactional ones like VoltDB were PC/EC. Labels describe a configuration at a date.

Likely follow-up: “Where would you choose EL?” Where a slightly stale answer is fine and speed matters: a product catalogue, a social feed’s like count. Not a bank balance.

5. Do quorums with R + W > N give strong consistency?

Show a strong answer

• They guarantee overlap, not linearizability. Abadi: a quorum protocol alone “is not sufficient to guarantee consistency to the level defined by Gilbert and Lynch.”
• Sloppy quorums write to whichever N nodes are healthy, not a fixed set. (Dynamo’s own common setting, (3,2,2), does satisfy R + W > N; it still isn’t linearizable.)
• Last-write-wins on timestamps loses updates when clocks disagree. Jepsen found QUORUM or ALL “does nothing to prevent it”.
• Abadi reports such systems typically ran R + W ≤ N for latency.
• The linearizable path in Cassandra-style systems is a Paxos lightweight transaction.

Likely follow-up: “Then why use quorums?” Durability and a good chance of fresh reads, cheaply. Just don’t call it linearizable.

6. A user refreshes a page and a comment they just saw disappears. What happened, and how do you fix it?

Show a strong answer

• A monotonic reads violation. Their second request went to a replica that was further behind than the first.
• Measured: a client alternating serializable reads between two etcd nodes during a partition saw the counter go 367, 229, 369, 229, going backwards 236 times.
• Fixes:
• keep each user on one replica (sticky sessions);
• have the client send the newest version it has seen, and have replicas wait or redirect until they’ve caught up;
• read from the leader.
• Monotonic reads is cheap: Jepsen classifies it as achievable even during a partition.

Likely follow-up: “And if the user wrote the comment?” Then it’s read-your-writes, a different guarantee, and a harder one to keep during a partition: the client has to stick to one server.

7. What does “eventually consistent” guarantee?

Show a strong answer

• Only that if writes stop, replicas converge. No definition bounds how long it takes.
• Measured: after the network recovered, the cut-off etcd node served stale reads for 2.4 to 2.5 more seconds, until it had caught up.
• Vendor figures, like DynamoDB’s “typically within a second or less”, are typical values, not guarantees.
• Design for it: tolerate staleness in reads, and use session guarantees where users would notice.

Likely follow-up: “What if writes never stop?” Then “eventually” may never arrive for a busy key. Gilbert and Lynch defined a separate, time-bounded model for exactly that reason.

8. Is Google Spanner a CA system?

Show a strong answer

• Technically no. Brewer, writing as Google’s VP of infrastructure: “It is technically a CP system.” During some partitions it chooses consistency and becomes unavailable.
• Effectively CA in practice, because Google’s private network makes partitions rare and availability is better than five nines.
• TrueTime doesn’t beat CAP. Brewer: it “does not significantly help achieve CA”. It provides external consistency, ordering transactions by commit time.
• The general lesson: high availability in practice (nines) and availability in CAP’s sense (every request, always) are different things.

Likely follow-up: “What does TrueTime do, then?” It bounds clock uncertainty, and Spanner waits out that uncertainty at commit so that timestamp order matches real-time order. That’s Part 25.

Sources

• Lab: system-design/checks/part24_consistency/etcd_lab.py, a three-node etcd 3.6.8 cluster in Docker, pinned by digest. It measures:
• read and write latency with and without 20 ms of delay between the nodes;
• three runs of cutting one follower off for ten seconds with dropped packets while a writer continues, with every operation logged and checked for stale reads, and the cut-off node’s Raft log position polled every 50 ms.
• Gilbert and Lynch, Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services, 2002, and Perspectives on the CAP Theorem, 2012.
• Eric Brewer:
• with Armando Fox, Harvest, Yield, and Scalable Tolerant Systems, 1999;
• Towards Robust Distributed Systems, PODC keynote, 2000;
• CAP Twelve Years Later: How the “Rules” Have Changed, IEEE Computer, 2012;
• Spanner, TrueTime & The CAP Theorem, 2017.
• Daniel Abadi, Consistency Tradeoffs in Modern Distributed Database System Design, IEEE Computer, 2012.
• Martin Kleppmann, A Critique of the CAP Theorem, 2015.
• Definitions:
• Herlihy and Wing, Linearizability, 1990.
• Lamport, How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs, 1979.
• Terry et al., Session Guarantees for Weakly Consistent Replicated Data, 1994.
• Werner Vogels, Eventually Consistent, 2008.
• Dynamo, 2007.
• Jepsen:
• consistency models;
• analyses of etcd 3.4.3 and Scylla 4.2.
• Vendor documentation:
• DynamoDB: read consistency and global tables.
• Cassandra 5.0: tunable consistency and guarantees.
• MongoDB 8.3: linearizable read concern.
• PostgreSQL 18: hot standby and replication.
• MongoDB 8.3: read concern and write concern.
• etcd: API guarantees, and the 3.6.8 source for the request timeout and linearizable reads.
• Google Cloud Spanner: external consistency.
• CockroachDB: FAQ and Living without atomic clocks.

What to remember

• During a partition, a node that can’t reach the majority can refuse or answer stale. It can’t answer correctly.
• etcd made that choice per request: during the cut, linearizable reads and writes went unanswered, and serializable reads all answered, all out of date.
• CAP’s C is linearizability, and its A is a response with no time limit. “Pick two of three” is wrong; Brewer said so.
• Unavailable looked mostly like silence: one read was held for the whole cut and then failed with a retryable error. Your timeout decides what happens next.
• PACELC’s else is the everyday cost: with 20 ms between nodes, linearizable reads took 42 to 83 ms, and local reads about 1.3 ms.
• Quorums overlap; they aren’t linearizable.
• “Strong consistency” means nothing until someone names the model.

A cut-off node can always be either wrong or silent. Decide which you’d rather it be before the network decides for you.