On this page

CAP Theorem

The CAP theorem is the most cited, most misunderstood, and most practically important result in distributed systems theory. It defines the fundamental trade-off that every distributed data store must navigate — and understanding it correctly separates engineers who design resilient systems from those who discover their trade-offs in production at 3 AM.

Historical Context

In 2000, Eric Brewer presented the CAP conjecture at the ACM Symposium on Principles of Distributed Computing (PODC). His claim: it is impossible for a distributed data store to simultaneously provide more than two out of three guarantees — Consistency, Availability, and Partition Tolerance.

In 2002, Seth Gilbert and Nancy Lynch of MIT formalized and proved Brewer's conjecture, turning it from a rule of thumb into a proven theorem. Their proof is surprisingly short — it constructs a specific scenario where providing all three is provably impossible.

In 2012, Brewer himself published "CAP Twelve Years Later: How the Rules Have Changed," clarifying widespread misunderstandings and introducing the idea that the trade-off is not a static choice but a dynamic, per-operation decision.

While the partition lasts, replica B has exactly two options: refuse reads (CP) or serve stale data (AP). There is no third choice — that's the theorem.

The Three Guarantees — Precisely Defined

Consistency (C)

Formal definition: Every read receives the most recent write or an error.

This is linearizability — the strongest form of consistency. It means the system behaves as if there is a single copy of the data, and all operations are atomic. If a write completes successfully, every subsequent read (from any node) must return that value or a later one.

Timeline:
  Client A: WRITE x=1     ────────────── OK
  Client B:                   READ x ──── returns 1 ✓
  Client C:                       READ x ─── returns 1 ✓

This is NOT the same as eventual consistency, where reads might return stale data for a while. CAP's "C" is the strongest possible guarantee.

Common Misconception

CAP consistency is NOT the same as ACID consistency. ACID consistency means transactions move the database from one valid state to another (integrity constraints). CAP consistency means all nodes see the same data at the same time (linearizability). These are completely different properties with the same name.

Availability (A)

Formal definition: Every request received by a non-failing node must result in a response (not an error).

There is no time bound on the response — it just must eventually come. But critically, this means the system cannot reject requests during a partition. If a node is up and receives a request, it must respond.

This does NOT mean low latency. A system that takes 30 seconds to respond is still "available" under CAP's definition. It also does NOT mean the response is correct — it just means a response is given.

Common Misconception

CAP availability is much stronger than practical availability (like "five nines"). CAP requires that EVERY non-failed node responds to EVERY request. Practical availability allows occasional failures. A system can have 99.999% uptime and still not satisfy CAP's availability guarantee.

Partition Tolerance (P)

Formal definition: The system continues to operate despite arbitrary message loss or delay between nodes.

A network partition occurs when the communication link between two or more nodes fails, splitting the cluster into isolated groups that cannot communicate with each other.

Before partition:
  [Node A] ←──── network ────→ [Node B]

During partition:
  [Node A] ←──── ✗ BROKEN ✗ ────→ [Node B]

  Both nodes are alive.
  Both nodes receive client requests.
  Neither node can communicate with the other.

In any real distributed system, network partitions WILL happen. Cables get cut. Switches fail. Cloud availability zones lose connectivity. Garbage collection pauses make a node appear dead. This is not a theoretical concern — it happens regularly in production.

The Precise Statement

The slogan "pick two of three" is catchy and mostly wrong. The theorem Gilbert and Lynch actually proved is narrower and sharper. It helps to state it the way they did.

The object. A single read/write register: one variable that supports read() and write(v). There are no transactions, no multi-key operations, and no queries. If CAP fails for one register, it fails for anything built on registers.

The consistency condition. Atomic consistency, which is another name for linearizability. Every operation appears to take effect at a single instant between its invocation and its response. All operations together form one total order that respects real time.

The availability condition. Every request received by a node that has not crashed must eventually get a response. Note "every" and "non-failing node". Returning an error counts as not responding. Redirecting the client to another node does not help if that node is unreachable.

The network. Asynchronous: there is no global clock and no bound on message delay. The network may lose arbitrarily many messages sent from one group of nodes to another. That arbitrary message loss is the partition. A partition is a property of the network, not a choice the system makes.

The theorem. In such a network, no algorithm can implement a read/write register that guarantees both atomic consistency and availability in every fair execution, including executions where messages are lost.

The corollary that matters more. Gilbert and Lynch add a second result. The impossibility holds even in executions where no message is actually lost, as long as messages can be arbitrarily delayed. A node waiting for a reply cannot tell "the message was lost" from "the message is slow". If it waits forever, it is unavailable. If it gives up and answers, it may be inconsistent. This is where CAP meets everyday engineering. Every timeout you configure is a decision about when to treat slowness as a partition.

TermIn everyday speechIn the theorem
Consistency"The data looks right"Linearizability of a single register
Availability"The service is up, 99.9%"Every request to every non-crashed node gets a non-error response
Partition tolerance"We handle network issues"Correctness must hold even when the network drops arbitrary messages between groups
"Choose two"Pick a column from a menuDuring a partition, a linearizable register cannot be totally available

The one-sentence version

When the network is partitioned, a system that is linearizable cannot keep every live node answering, and a system that keeps every live node answering cannot be linearizable. When there is no partition, CAP says nothing at all.

These definitions build on the vocabulary in System Models: asynchronous versus partially synchronous networks, crash failures, and fair executions. CAP and FLP are cousins. Both say that in an asynchronous network you cannot tell slow from dead, and both are escaped in practice by assuming the network is eventually well behaved.

The Proof (Simplified)

Gilbert and Lynch's proof is by contradiction. Assume a system provides all three guarantees. Now construct a scenario:

Setup: Two nodes, and , both storing value .

Step 1: A network partition occurs — and cannot communicate.

Step 2: A client sends a write request to : WRITE v = v_1

Step 3: Because the system is Available, must respond with success (it cannot reject the request just because it can't reach ).

Step 4: Because the system is Partition Tolerant, it must continue operating despite the partition. processes the write.

Step 5: A different client sends a read request to : READ v

Step 6: Because the system is Available, must respond (it cannot refuse).

Step 7: But has no way to know about the write to (the partition prevents communication). So returns .

Step 8: This violates Consistency — a read returned after a write set .

QED. No system can provide all three simultaneously during a partition.

The same execution as a sequence diagram:

sequenceDiagram
    participant C1 as Client 1
    participant N1 as Node N1
    participant N2 as Node N2
    participant C2 as Client 2
    Note over N1,N2: Both hold v0. The network now drops every N1-N2 message.
    C1->>N1: write(v1)
    N1--xN2: replicate v1 (lost)
    Note over N1: Availability forces a reply without hearing from N2
    N1-->>C1: ok
    C2->>N2: read()
    Note over N2: Availability forces a reply. N2 has seen only v0.
    N2-->>C2: v0
    Note over C1,C2: The write of v1 finished before the read began, so linearizability requires v1. Contradiction.

Why the proof is so short

The argument works because it uses only three facts:

  1. Indistinguishability. From N2's point of view, the execution where C1 wrote v1 to N1 looks exactly like the execution where nobody wrote anything. N2 received the same messages in both: none. An algorithm can act only on what a node has seen, so N2 must answer the same way in both executions.
  2. Availability forces a decision. N2 cannot wait for the partition to heal, because nothing in the model says it ever will. It must answer with what it has.
  3. Real-time order. Linearizability respects wall-clock order between operations that do not overlap. The write completed before the read started, so the read must return v1.

All the clever-sounding escape hatches fail one of these three. "N2 could forward the read to N1": the forward is lost. "N1 could refuse the write until N2 acknowledges": then N1 is unavailable. "The client could talk to both": that is just another message over the partition.

What the proof does not show

  • It does not show that partitioned systems must be useless. The minority side can still serve stale reads that are labelled as stale. The majority side of a consensus group can keep serving everything.
  • It does not show that consistency and availability conflict when the network is healthy. Without lost or delayed messages, the construction has nothing to work with.
  • It does not apply to consistency models weaker than linearizability in the same way. Some weaker models are achievable with full availability (see What Is Achievable During a Partition).
Full Formal Proof

The formal proof in Gilbert & Lynch's paper uses an asynchronous network model where:

  • Messages can take arbitrarily long to deliver
  • There are no bounds on processing time
  • The only guarantee is that messages sent over a non-partitioned link are eventually delivered

In this model, they show that for any algorithm claiming to implement an atomic (linearizable) read/write register:

  1. There exists an execution containing a partition where some read operation returns an inconsistent value, OR
  2. There exists an execution where some operation never receives a response

This holds even for a single register storing a single bit. The result is surprisingly strong — it applies to the simplest possible case.

The formal proof distinguishes between asynchronous and partially synchronous models. Gilbert and Lynch show the impossibility still holds in their partially synchronous model, where nodes have local clocks, whenever messages can be lost. What partial synchrony buys is a weaker but useful guarantee they call delayed-t consistency. When no messages are lost, the system is fully consistent. While messages are being lost, reads may be stale, but only in a bounded way, and the system converges once the partition heals. Real systems work the same way: consistent and available when the network is healthy, and degrading in a controlled way during a partition.

The Real Trade-Off: CP vs AP

Since network partitions are inevitable in any distributed system, "Partition Tolerance" is not really a choice — you MUST have it. The real question becomes:

During a partition, do you sacrifice Consistency or Availability?

CP Systems (Consistency + Partition Tolerance)

When a partition occurs, some nodes will become unavailable to maintain consistency.

Behavior during partition:

  • Nodes that can't confirm they have the latest data will refuse requests (return errors)
  • The system prefers being correct over being responsive
  • Some clients may see errors or timeouts

Examples:

SystemHow It Works
ZooKeeperUses ZAB consensus. During a partition, the minority side stops accepting writes. Clients connected to minority nodes get errors.
etcdUses Raft consensus. A leader must be able to communicate with a majority. If partitioned away from the majority, the old leader steps down.
HBaseUses ZooKeeper for coordination. Region servers cut off from ZooKeeper stop serving requests.
MongoDB (default)With w:majority, writes only succeed if acknowledged by a majority. During a partition, the minority side cannot accept writes.
SpannerGoogle's globally distributed database. Uses TrueTime and Paxos. Sacrifices availability during partitions to provide external consistency (strongest form of linearizability).

When to choose CP:

  • Financial transactions (you cannot have two nodes accepting conflicting transfers)
  • Inventory management (overselling is worse than temporary unavailability)
  • Leader election (two leaders is catastrophic — "split-brain")
  • Configuration management (nodes acting on different configs causes cascading failures)

AP Systems (Availability + Partition Tolerance)

When a partition occurs, all nodes continue serving requests, but may return stale or conflicting data.

Behavior during partition:

  • All nodes respond to all requests
  • Different nodes may return different values for the same key
  • After the partition heals, the system must reconcile conflicting updates

Examples:

SystemHow It Works
CassandraTunable consistency. With ONE read/write consistency, every node responds. During partitions, updates happen on both sides and are reconciled using last-write-wins (LWW) timestamps.
Dynamo (the 2007 paper design)Amazon's internal key-value store. Uses consistent hashing, sloppy quorums and vector clocks. During partitions, all reachable nodes continue serving. Conflicting versions are returned on read and merged by application-supplied logic.
DynamoDB (default reads)Amazon's managed service. Despite the name, it is not the Dynamo paper design: each partition has a leader replica elected with Multi-Paxos. Default reads are eventually consistent and can be served by any replica. Strongly consistent reads and all writes go through the leader (see below).
CouchDBMulti-master replication. Every node accepts writes independently. Conflicts stored and exposed to the application for resolution.
RiakDynamo-style. Vector clocks (later dotted version vectors) track causality. Concurrent writes are kept as siblings, which are presented to the application for merging. Since Riak 2.0 it also offers convergent data types (CRDTs: counters, sets, maps) that merge automatically.
DNSThe most successful AP system ever built. DNS records propagate slowly and can be stale, but every DNS server always responds.

When to choose AP:

  • Social media feeds (showing a slightly stale feed is better than showing nothing)
  • Shopping carts (let users add items on both sides of a partition, merge later)
  • Caching layers (stale cache is better than no cache — usually)
  • Metrics/analytics (approximate counts are acceptable, downtime is not)
  • Session stores (a slightly stale session is better than logging the user out)

Neither CP nor AP

A third category is easy to miss: systems that satisfy neither definition. Take a common setup: a primary database with asynchronous replicas, where clients read from replicas and an orchestrator promotes a replica when the primary looks dead.

  • It is not linearizable. Replica reads can be stale even with no partition, and an asynchronous failover can lose writes the old primary acknowledged.
  • It is not CAP-available. A replica cut off from the primary cannot accept writes.

Many popular deployments sit here. That is not a design failure. It is an honest trade for low latency and simplicity. But calling such a system "CP" because it has a single leader, or "AP" because replicas keep serving reads, misdescribes it. Martin Kleppmann's 2015 essay "Please stop calling databases CP or AP" makes this argument at length.

How Real Systems Classify Themselves

Vendors and papers describe their systems in CAP terms, and the descriptions are more nuanced than the labels in the tables above. Here is how five well-known systems behave. Each describes the default or a documented configuration. Details change between versions, so check the documentation of the version you run.

Spanner

Spanner replicates each split (a contiguous key range) with a Paxos group, and commits transactions only when a majority of the group's replicas accept them. TrueTime lets it assign commit timestamps that respect real-time order, which gives external consistency (strict serializability). During a partition, a replica group without a majority stops making progress. By the theorem's definition, Spanner is CP.

Eric Brewer, who by then worked at Google, wrote a 2017 paper arguing that Spanner is nonetheless "effectively CA". His argument is not that Spanner beats the theorem. It is that Google's private network, with redundant paths and careful operations, makes partitions rare enough that Spanner's measured availability exceeds five nines. Most outages users do experience come from other causes, such as bugs and overload. The paper is a useful corrective: CAP describes what happens during a partition, and how often partitions happen is an engineering variable.

DynamoDB

The name invites confusion with the 2007 Dynamo paper, but the managed service works differently. The 2022 USENIX ATC paper on DynamoDB describes each table partition as a replication group of three replicas in different Availability Zones, with a leader elected using Multi-Paxos. Writes go to the leader and are acknowledged once a quorum has persisted them to its write-ahead log.

OperationServed byDuring a partition that isolates a replica
WriteLeader, quorum-acknowledgedSucceeds if the leader and a quorum can communicate. Otherwise fails until a new leader is elected.
Eventually consistent read (default)Any replicaSucceeds, possibly stale
Strongly consistent read (ConsistentRead: true)LeaderFails or retries if the leader is unreachable
Global tables (multi-Region, default mode)Local Region, replicated asynchronouslyEach Region keeps accepting writes. Conflicts resolve last-writer-wins.

So a single DynamoDB table offers a CP path (writes, strong reads) and an AP-flavoured path (default reads), chosen per request. Classic global tables are PA/EL across Regions. AWS has since added a multi-Region strong consistency mode for global tables. It trades cross-Region latency for linearizable reads, which is the PACELC trade in action.

// AWS SDK v3: the same table, two different trade-offs
import { DynamoDBClient, GetItemCommand } from "@aws-sdk/client-dynamodb";

const ddb = new DynamoDBClient({ region: "us-east-1" });

// Default: eventually consistent, cheaper, served by any replica
await ddb.send(new GetItemCommand({
  TableName: "accounts",
  Key: { id: { S: "acct-42" } },
}));

// Strongly consistent: served by the partition leader, costs twice the read capacity
await ddb.send(new GetItemCommand({
  TableName: "accounts",
  Key: { id: { S: "acct-42" } },
  ConsistentRead: true,
}));

Cassandra

Cassandra is leaderless. Every replica of a key can accept reads and writes, and the client chooses a consistency level per request. Conflicts between concurrent writes resolve last-write-wins by cell timestamp. Hinted handoff, read repair and anti-entropy repair (nodetool repair) bring replicas back into agreement after failures. See Quorums and Leaderless Replication for the mechanics.

Consistency levelWaits forPartition behaviour (RF = 3)
ONE1 replicaAvailable on any side that can reach one replica. Reads may be stale.
QUORUM2 of 3 replicas across the clusterOnly a side holding 2 replicas can serve.
LOCAL_QUORUMMajority in the coordinator's datacenterEach datacenter keeps working when the inter-DC link fails.
ALLAll 3Any single unreachable replica causes failure.
SERIAL / LOCAL_SERIALPaxos round among replicasUsed by lightweight transactions (IF NOT EXISTS, IF col = x). Needs a majority.
-- cqlsh: session-level consistency
CONSISTENCY QUORUM;
UPDATE carts SET items = items + {'sku-9'} WHERE user_id = 42;

-- Compare-and-set via a lightweight transaction (Paxos under the hood)
INSERT INTO usernames (name, user_id) VALUES ('ayush', 42) IF NOT EXISTS;

Even QUORUM reads and writes are not fully linearizable in Cassandra. LWW timestamps come from clocks that can skew, and a write that fails at the client may still have landed on one replica and spread later. Cassandra is best described as "tunable, with a linearizable compare-and-set available through Paxos", not as AP or CP.

etcd

etcd is a Raft group, usually of three or five members, and it is the canonical CP system. A write commits when a majority of members persist it. A member partitioned into a minority cannot elect a leader, so it cannot accept writes. The old leader, if it lands in the minority, stops being able to commit.

Reads come in two flavours:

Read typeHow it worksPartition behaviour
Linearizable (default)The member confirms with a quorum that its view is current (Raft ReadIndex) before answeringFails on the minority side
SerializableAnswered from the member's local state with no quorum round tripSucceeds on the minority side, possibly stale
# Linearizable read: goes through a quorum check
etcdctl get /config/feature-flags

# Serializable read: local, fast, possibly stale
etcdctl get /config/feature-flags --consistency=s

Kubernetes stores all cluster state in etcd. That is why a control plane that loses etcd quorum stops accepting changes (no new pods, no updated deployments) while existing workloads keep running. The data plane does not need etcd to keep serving.

ZooKeeper

ZooKeeper orders writes through its leader using the Zab protocol, and a write commits on a quorum. Reads, however, are served locally by whichever server the client is connected to. That makes reads sequentially consistent, not linearizable: a client can read a value that is behind a write another client has already seen acknowledged. A client that needs the latest value calls sync() before reading. A server cut off from the quorum stops serving clients, and the clients reconnect elsewhere. See the Zab protocol page for the details.

Summary

SystemReplication coreCAP behaviour during a partitionPACELC (typical)
SpannerPaxos per split + TrueTimeCP. Minority groups stall.PC/EC
DynamoDB (single Region)Multi-Paxos leader per partitionWrites and strong reads CP. Default reads stay available but may be stale.PC/EL by default, PC/EC with strong reads
DynamoDB global tables (default)Async multi-Region, LWWAP across RegionsPA/EL
CassandraLeaderless, per-request consistency levelDepends on level: ONE is AP-like, QUORUM needs a majorityPA/EL at ONE, PC/EC at QUORUM
etcdRaftCP. Minority refuses writes and linearizable reads.PC/EC
ZooKeeperZabCP for writes. Reads are local and can lag.PC/EL for reads, PC/EC for writes

Beyond the Binary: The PACELC Model

Daniel Abadi proposed PACELC in 2012 to extend CAP with the observation that even when there is NO partition, there is still a trade-off between latency and consistency.

PACELC: If there is a Partition, choose between Availability and Consistency. Else (no partition), choose between Latency and Consistency.

if (partition) {
  choose: Availability OR Consistency    // CAP trade-off
} else {
  choose: Latency OR Consistency         // PACELC extension
}

This captures important nuances:

SystemPartition (PA/PC)No Partition (EL/EC)Classification
Cassandra (ONE)PAELPA/EL — always fast, sometimes inconsistent
MongoDB (majority)PCECPC/EC — always consistent, sometimes slow
DynamoDBPAELPA/EL — prioritizes availability and speed
SpannerPCECPC/EC — consistency above all else
Cassandra (QUORUM)PCECPC/EC — a minority side cannot form a quorum, and every request waits for a quorum even with no partition
PNUTS (Yahoo)PCELPC/EL — timeline consistency with low latency

War Story

At Amazon, the original Dynamo paper (2007) made the deliberate choice of PA/EL for the shopping cart service. The reasoning: a customer should NEVER see an error when adding to their cart. If a partition occurs and both sides accept conflicting cart updates, the reconciliation strategy is to take the union of both carts. The worst case is that an item the customer removed reappears — annoying but recoverable. The alternative (CP) would mean the customer sees an error page during checkout, which directly costs revenue.

This single design decision — choosing AP for the shopping cart — influenced an entire generation of distributed database design and directly led to Cassandra, Riak, and Voldemort.

Why PACELC is the more useful lens

Partitions are rare compared with ordinary requests. A system might see a handful of partition events a year and billions of requests every day. The "else" branch of PACELC, the latency-versus-consistency trade, applies to every one of those requests. The "if partition" branch applies only during incidents. If you are choosing a database for a latency-sensitive product, the ELC half usually matters more to your users than the PAC half.

The two halves are also independent. Some systems give up consistency on both branches (PA/EL), some give it up on neither (PC/EC), and some mix:

  • PA/EC is unusual but exists. Abadi cited MongoDB's configuration at the time. A system can be strongly consistent in normal operation and fall back to accepting divergent writes during a partition.
  • PC/EL is what PNUTS did, and what a ZooKeeper read does: refuse to diverge during a partition, but serve reads locally (and possibly stale) in normal operation to keep latency low.

Latency vs Consistency

Why does consistency cost latency when nothing is broken? Because linearizability needs coordination. Before a write is acknowledged, enough replicas must hear about it that any later read is guaranteed to see it. That takes at least one round trip from the coordinator to a quorum. A strongly consistent read either needs a round trip too (to confirm nothing newer exists) or needs a lease that guarantees it (see Leases and Fencing).

The cost of one round trip depends on where the replicas are:

Replica placementTypical round-trip timeCost of one quorum round trip
Same host or rackTens of microsecondsNegligible next to disk fsync
Across Availability Zones in one regionRoughly 0.5–2 msNoticeable, usually acceptable
Across regions on one continent (e.g. US East to US West)Roughly 60–80 msDominates request latency
Intercontinental (e.g. US to Asia-Pacific)Roughly 150–250 msOften unacceptable for interactive writes

These figures are approximate and vary with provider and route. The physics does not vary: light in fibre covers about 200 km per millisecond, so New York to London (about 5,600 km) costs at least roughly 56 ms for a round trip, before any routing or queuing.

The latency math of a quorum

With replicas and a majority quorum , the coordinator waits for the -th fastest acknowledgement, counting its own. The commit latency is therefore the -th smallest round-trip time to the other replicas:

This has a counterintuitive consequence for placement. Take five replicas in us-east, us-east, us-west, eu-west and ap-south, with the leader in us-east. The quorum is 3, so the leader needs two remote acknowledgements. The other us-east replica answers in about 1 ms. The second-fastest is us-west at about 70 ms. Commit latency is around 70 ms, and the slow Asia replica never sits on the critical path. Move the second us-east replica to Asia and the second acknowledgement now comes from Europe or Asia, so latency jumps. Where you put the majority determines your write latency.

Ways systems buy back latency

TechniqueWhat it gives upExample
Read from any replicaRead-your-writes and linearizabilityDynamoDB default reads, etcd serializable reads
Leader leasesCorrectness depends on bounded clock driftRaft-based stores serving reads at the leaseholder (CockroachDB, TiKV)
Follower reads at a past timestampFreshness (bounded staleness)Spanner stale reads, CockroachDB AS OF SYSTEM TIME
Regional quorumsGlobal linearizability across regionsCassandra LOCAL_QUORUM
Session guaranteesOnly per-client ordering, not globalRead-your-writes via sticky routing or version tokens (see Replication)

The PACELC question to ask in a design review

"For this operation, would we rather wait one cross-region round trip, or occasionally return a value that is a few hundred milliseconds old?" Ask it per operation, not per database.

Per-Operation Trade-offs

One of the most important insights from Brewer's 2012 revisit is that CAP is not a system-wide, static choice. Different operations in the same system can make different trade-offs:

// Same database, different trade-offs per operation

// CP: Account balance must be consistent (financial correctness)
async function getAccountBalance(userId: string): Promise<number> {
  return await db.read('accounts', userId, {
    consistency: 'strong',     // linearizable read
    // If partition occurs, this will return an error rather than stale data
  });
}

// AP: User profile can be eventually consistent (stale is acceptable)
async function getUserProfile(userId: string): Promise<Profile> {
  return await db.read('profiles', userId, {
    consistency: 'eventual',   // might be stale
    // If partition occurs, returns whatever data this node has
  });
}

// AP: Activity feed — availability over consistency
async function getActivityFeed(userId: string): Promise<Activity[]> {
  return await db.read('feeds', userId, {
    consistency: 'eventual',
    maxStaleness: '5s',        // bounded staleness — read at most 5s behind
  });
}

This is how production systems actually work. The question is never "is this system CP or AP?" but "for THIS operation, on THIS data, which trade-off is correct?"

Tunable Consistency (Quorum Systems)

Many distributed databases let you tune the consistency/availability trade-off per request using quorum-based reads and writes.

Given replicas, write replicas, and read replicas:

Common configurations:

ConfigurationWRNBehavior
Strong consistencyN1NWrite to all, read from any. Write is slow, read is fast.
Strong consistency⌈N/2⌉+1⌈N/2⌉+1NQuorum read + write. Balanced latency.
Weak consistency11NWrite to one, read from one. Fastest but no consistency guarantee.
Write-optimized1NNWrite to one (fast writes), read from all (slow reads, but consistent).

Example with N=3:

Strong consistency: W=2, R=2 (2+2=4 > 3 ✓)

Write: goes to 2 of 3 nodes → acknowledged
Read: goes to 2 of 3 nodes → at least 1 has latest value

  [Node A: v=1] ✓ (received write)
  [Node B: v=1] ✓ (received write)
  [Node C: v=0] ✗ (hasn't received write yet)

Read hits Node B and Node C:
  Node B returns v=1 (latest)
  Node C returns v=0 (stale)
  Client takes the one with the higher timestamp → v=1 ✓

The math for determining the probability of stale reads with different quorum sizes:

For :

For :

A Worked Partition Scenario

Abstract arguments only go so far, so let's trace one concrete incident through two designs.

The setup. A ticketing service sells seats for a concert. Seat state lives in a replicated store with five replicas spread over three Availability Zones:

ZoneReplicas
AZ-aR1, R2
AZ-bR3, R4
AZ-cR5

Application servers run in every zone and talk to the store replicas nearby. At T = 0, a misconfigured network change cuts AZ-c off from AZ-a and AZ-b. Clients on the public internet can still reach the application servers in AZ-c. The partition lasts 90 seconds.

Two customers want seat 14F. Alice is routed to AZ-a and Bob to AZ-c.

Design 1: CP, a Raft group

The five replicas form a single Raft group. Before the partition, the leader was R1 in AZ-a.

sequenceDiagram
    participant Alice
    participant R1 as R1 (leader, AZ-a)
    participant Maj as R2-R4 (AZ-a, AZ-b)
    participant R5 as R5 (AZ-c)
    participant Bob
    Note over R1,R5: T=0 partition isolates AZ-c
    Alice->>R1: reserve 14F
    R1->>Maj: AppendEntries(reserve 14F)
    Maj-->>R1: ack from 3 followers
    Note over R1: Committed on 4 of 5, majority holds
    R1-->>Alice: reserved
    Bob->>R5: reserve 14F
    Note over R5: Not the leader and cannot reach it
    R5-->>Bob: error, retry later
    Note over R5: Election timeout. R5 votes for itself and gets 1 of 5 votes.
    Note over R1,R5: T=90s partition heals. R5 sees the higher log and catches up.
    Bob->>R5: reserve 14F
    R5-->>Bob: seat already taken
TimeAZ-a/AZ-b (majority, 4 replicas)AZ-c (minority, 1 replica)
T+0 sLeader R1 keeps committing with 4 of 5R5 stops receiving heartbeats
T+0.3 sAlice's reservation commitsR5's election timer fires. It becomes a candidate, gets only its own vote and retries with higher terms.
T+0–90 sFully availableEvery write fails. Linearizable reads fail. Bob sees errors.
T+90 sUnchangedR5 receives a heartbeat from R1, sees R1's term, steps down and replicates the missing entries

Outcome. No double-sale, ever. Bob's experience is worse: 90 seconds of errors unless the load balancer notices that AZ-c's application servers return errors and routes him elsewhere. That rerouting is the practical way CP systems hide minority-side unavailability. The client goes to the majority.

There is a subtlety at T+0.3 s. With the Raft PreVote extension (used by etcd and others), R5 first asks whether it could win before bumping its term. When the partition heals, it then does not force R1 to step down with a higher term. Without PreVote, R5's inflated term makes R1 step down, which causes a brief election storm.

Design 2: AP, a leaderless store at consistency level ONE

The five replicas form a leaderless cluster, and seat 14F has replication factor 3 with replicas on R1, R3 and R5. Clients read and write at ONE.

sequenceDiagram
    participant Alice
    participant R1 as R1 (AZ-a)
    participant R3 as R3 (AZ-b)
    participant R5 as R5 (AZ-c)
    participant Bob
    Note over R1,R5: T=0 partition isolates AZ-c
    Alice->>R1: read 14F
    R1-->>Alice: free
    Bob->>R5: read 14F
    R5-->>Bob: free
    Alice->>R1: write 14F=alice at ts 1000
    R1->>R3: replicate
    R1--xR5: replicate (lost, hint stored)
    R1-->>Alice: ok
    Bob->>R5: write 14F=bob at ts 1003
    R5--xR1: replicate (lost, hint stored)
    R5-->>Bob: ok
    Note over R1,R5: T=90s heal. Hints replay. LWW keeps ts 1003.
    Note over Alice: Alice holds a confirmation for a seat that is now Bob's
TimeAZ-a/AZ-bAZ-c
T+0–90 sFully availableFully available
T+10 sAlice reserves 14F (timestamp 1000)
T+13 sBob reserves 14F (timestamp 1003)
T+90 sHinted handoff delivers Bob's write. LWW: 1003 > 1000, so R1 and R3 now say "bob".Hint delivers Alice's write. 1000 < 1003, so it is discarded.

Outcome. Every request succeeded, and the system sold one seat twice. Last-write-wins then silently discarded Alice's acknowledged write. If the two application servers' clocks had been skewed by more than three seconds, the earlier reservation could have won instead, which is arguably worse.

Design 3: AP with explicit conflict handling

Some businesses do prefer availability for this. An airline accepts that overbooking happens and handles it with compensation. The AP design can be made honest:

  1. Store both concurrent reservations as siblings instead of applying LWW. This needs version vectors or a set-valued register (see Causality and Version Vectors).
  2. When the partition heals, a reconciliation job detects the sibling set {alice, bob} for seat 14F.
  3. A deterministic rule picks the winner, for example the earliest payment-authorisation ID.
  4. The loser gets a business-level compensation: an apology, an upgrade, a refund.

That is the pattern Brewer's 2012 paper calls partition recovery with compensation. It is the same pattern banks use for ATMs that dispense cash while offline, up to a limit.

What the scenario teaches

QuestionCP answerAP (LWW) answerAP (siblings + compensation) answer
Who sees errors?Clients pinned to the minority sideNo oneNo one
Can the invariant "one owner per seat" break?NoYes, silentlyYes, detected and repaired
Is any acknowledged write lost?NoYesNo
Extra work requiredClient rerouting, retriesNone (that is the trap)Version tracking, reconciliation, a compensation process

The real choice was never "C or A" in the abstract. It was "is a duplicate seat sale worse than 90 seconds of errors for one AZ's users?" For concert tickets the answer is usually yes, so choose CP and reroute clients. For a "like" counter the answer is no, so choose AP with a CRDT counter.

What Is Achievable During a Partition

CAP rules out linearizability with total availability. It does not rule out everything. Several research results map out exactly what an always-available system can provide:

GuaranteeAchievable with total availability?Notes
LinearizabilityNoCAP itself
Sequential consistencyNoAlso requires coordination
Serializability, snapshot isolationNoBailis et al., "Highly Available Transactions" (VLDB 2014)
Causal consistencyYesMahajan, Alvisi and Dahlin (2011) argue that real-time causal consistency is the strongest model achievable in an always-available, convergent system
Read committed, monotonic atomic viewYesHAT paper
Read-your-writes, monotonic readsYes, if the client sticks to one replica ("sticky availability")HAT paper. Lose the sticky replica and you lose the guarantee.
Eventual convergenceYesNeeds a deterministic merge: LWW, CRDTs, or application logic

This table is more useful than the CP/AP split. A shopping cart needs causal consistency plus a merge, which is achievable. A bank transfer needs serializability on two balances, which is not achievable with total availability, so it must be CP or use compensation.

Operating Through a Partition

Brewer's 2012 revisit describes partition handling as three steps, and real systems implement each one explicitly.

stateDiagram-v2
    [*] --> Normal
    Normal --> PartitionMode: timeout, peer unreachable
    PartitionMode --> PartitionMode: serve permitted ops, log intents
    PartitionMode --> Recovery: connectivity restored
    Recovery --> Normal: state merged, invariants repaired
  1. Detect the partition. There is no partition signal, only a timeout. The timeout you pick is the point where you decide that slow means partitioned. Too short and you flap into partition mode on every GC pause. Too long and every request waits out the timeout first. See Timeouts, Retries and Backoff.
  2. Enter partition mode. Decide per operation what is still allowed. A common split: reads allowed and marked possibly-stale, commutative writes allowed (incrementing a counter, adding to a set), and invariant-sensitive writes refused or limited (charging a card, assigning a unique username). Record everything done in partition mode so it can be replayed.
  3. Recover. When connectivity returns, merge the two sides' state, check invariants, and compensate for any violations. The merge is easy for CRDTs, harder for application objects, and impossible to automate for some business rules. That last group goes to a human queue.

Bounded availability is a design tool

You do not have to choose between "refuse everything" and "accept everything". An ATM network may let an offline machine dispense up to a fixed amount per card. A seat-booking system could pre-assign a block of seats to each zone, so each side can sell its own block without coordination. Splitting a global invariant into per-partition budgets ("escrow") keeps both sides available and keeps the invariant intact.

Practical Decision Framework

When designing a distributed system, work through this decision tree:

graph TD
    A[What happens if two clients<br/>see different values?] --> B{Financial loss<br/>or data corruption?}
    B -->|Yes| C[Choose CP]
    B -->|No| D{Users notice<br/>or are annoyed?}
    D -->|They notice but<br/>it's tolerable| E[Choose AP with<br/>bounded staleness]
    D -->|They won't<br/>notice| F[Choose AP with<br/>eventual consistency]
    C --> G{Latency<br/>critical?}
    G -->|Yes| H[Use quorum reads<br/>W=majority R=majority]
    G -->|No| I[Use synchronous<br/>replication]
    E --> J[Set maxStaleness<br/>based on use case]
    F --> K[Use async replication<br/>with conflict resolution]

    style C fill:#ff6b6b,color:#fff
    style E fill:#ffd43b,color:#000
    style F fill:#51cf66,color:#fff

Common Mistakes

Mistake 1: "We chose CP so we're always consistent"

CP systems are only consistent IF the system is working correctly. During a partition, a CP system provides consistency by sacrificing availability — meaning some requests fail. If your error handling swallows those failures or retries against a stale cache, you've accidentally become AP without the proper conflict resolution.

Mistake 2: "We need strong consistency everywhere"

Most data in most applications doesn't need linearizability. Profile pictures, display names, notification counts, activity feeds, analytics data, cached content — all of these are perfectly fine with eventual consistency. Reserve strong consistency for data where incorrectness causes real harm: money, inventory, permissions, leader election.

Mistake 3: "AP means we lose data"

AP does not have to mean losing data. An AP system may temporarily return stale data or need to reconcile conflicts. Merge-based strategies (vector clocks with application merging, CRDTs) keep every concurrent update. The Dynamo paper describes the shopping cart this way: concurrent versions are merged, so an "add to cart" is never lost, though a deleted item can reappear.

The caveat is last-write-wins. LWW resolves a conflict by keeping one version and silently throwing the other away. A store that is AP and LWW does lose acknowledged writes during a partition, and it does so by design. Know which resolution strategy you are running.

Mistake 4: "Network partitions are rare, so CAP doesn't matter"

Bailis and Kingsbury's survey "The Network is Reliable" (ACM Queue, 2014) collects dozens of publicly reported partitions. The causes include switch failures, misconfigured firewalls, NIC firmware bugs, and long GC pauses that made healthy nodes look dead. At scale, partitions are a normal operating condition, not a rare one. Design for them.

Correction: an earlier version of this paragraph attributed a "partitions multiple times per day" statistic to Google's Chubby paper. We could not verify that attribution, so the claim now points to a source that documents partition frequency directly.

Mistake 5: "We picked our trade-off so we're done"

The trade-off is not static. It should be revisited:

  • When requirements change (new regulatory requirements may demand strong consistency for data that was previously eventually consistent)
  • When scale changes (what worked at 10 nodes may not work at 1000)
  • When new operations are added (a new feature may need a different trade-off than existing features)

Mistake 6: "We're a CA system"

A single-node database is CA only in a trivial sense: there is no network to partition. Once data is on two machines, the partition will happen whether or not you planned for it. "CA" in practice means "we didn't decide", and the system's real behaviour is whatever its timeouts happen to do.

Mistake 7: "CAP says AP systems converge"

CAP is silent about convergence. An AP system that never reconciles is still CAP-available. Convergence comes from anti-entropy and a deterministic merge, and you have to build it yourself.

War Story: GitHub, October 2018

On 21 October 2018, GitHub lost connectivity for 43 seconds between its US East Coast network hub and its primary East Coast data centre. Its MySQL failover tooling, Orchestrator, promoted replicas in the West Coast data centre. When connectivity returned, the East Coast primaries held a few seconds of writes that had never replicated west, and new writes were already landing in the West. GitHub chose consistency over availability during repair. It ran degraded for about 24 hours while restoring from backups and reconciling the divergent writes, instead of discarding either side. GitHub's public post-incident analysis is worth reading in full. A 43-second partition, a timeout-driven failover, and a topology that was neither CP nor AP produced a day-long incident.

Interview Questions

1. State the CAP theorem precisely. What is "C", and what is "A"?

C is linearizability of a single register. A means every request to a non-crashed node eventually gets a non-error response. The theorem: in an asynchronous network that can lose messages, you cannot have both. It says nothing about systems without partitions.

2. Sketch the Gilbert-Lynch proof.

Two nodes are partitioned. A write to N1 must be acknowledged (availability). A later read at N2 must be answered (availability), but N2 cannot distinguish this execution from one with no write, so it returns the old value. That violates linearizability.

3. Why is "pick any two" misleading?

P is not optional in a distributed system, and the choice applies only while a partition lasts. It can also be made per operation. Many real systems are neither CP nor AP.

4. Classify etcd, DynamoDB and Cassandra.

etcd is CP: Raft, minority refuses writes, and the default reads are linearizable. DynamoDB: writes and strong reads go through a Paxos leader (CP), while default reads may be stale. Cassandra depends on the consistency level: ONE is AP-like with LWW, QUORUM needs a majority, and LWTs use Paxos.

5. What does PACELC add, and why does it matter more day to day?

The latency/consistency trade when there is no partition. It applies to every request, not just during incidents. Linearizable operations pay at least one quorum round trip.

6. Five replicas across three regions. How do you minimise write latency while staying CP?

Place a majority (three replicas) close together, for example two in the leader's region and one in a nearby region. Commit then waits only for nearby acknowledgements. The far replicas give durability and serve stale reads.

7. What consistency can an always-available system offer?

Causal consistency, read committed, and monotonic atomic view. With sticky clients, also read-your-writes and monotonic reads. It cannot offer serializability, snapshot isolation or linearizability.

8. Your AP store uses LWW. What goes wrong during a partition, and how would you fix it?

Concurrent writes on both sides are acknowledged, and one is silently discarded on heal. Clock skew can even pick the earlier write. Fixes: siblings or version vectors with an application merge, CRDTs, or routing invariant-sensitive operations through a CP path such as a Paxos compare-and-set.

Further Reading

  • Gilbert & Lynch's proof: Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services (2002)
  • Brewer's 2012 revisit: "CAP Twelve Years Later: How the Rules Have Changed"
  • Abadi's PACELC: "Consistency Tradeoffs in Modern Distributed Database System Design"
  • Amazon's Dynamo paper: "Dynamo: Amazon's Highly Available Key-value Store" (2007)
  • Brewer (2017): "Spanner, TrueTime and the CAP Theorem" — Google's own account of why Spanner is CP but "effectively CA"
  • Kleppmann (2015): "Please stop calling databases CP or AP" and "A Critique of the CAP Theorem"
  • Bailis & Kingsbury (2014): "The Network is Reliable" — a catalogue of real partitions
  • Bailis et al. (VLDB 2014): "Highly Available Transactions: Virtues and Limitations"
  • Elhemali et al. (USENIX ATC 2022): "Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service"
  • Next: Consistency Models — understanding the spectrum between linearizability and eventual consistency
  • Related: System Models, FLP Impossibility, Quorums and Leaderless Replication, Replication, Leases and Fencing