Components of CAP Theorem

Consistency, Availability and Partition-tolerance are not three switches you flip on — each is a precise, mechanically testable guarantee about how one node's response relates to operations happening elsewhere, and each is really the top of a spectrum of weaker versions. The introduction settled why a partition forces you to drop C or A; this page dissects the three letters themselves, so you can say exactly what a system is promising, how you would catch it lying, and how strong a version of each you actually need.

Consistency (C): a single-copy illusion, defined as linearizability

The mechanism: a read or write appears to take effect atomically at one instant between the moment you call it and the moment it returns, and those instants respect real time — if operation A finishes before B starts, every replica must order A before B. Equivalently, the whole cluster behaves as if there were exactly one copy of the data. That is linearizability, and it is the C in CAP.

Crucially, C is not binary in practice — it is the strongest rung of a ladder: linearizable > sequential > causal > eventual. Each rung drops a promise. Sequential keeps a single global order but lets it drift from real-time; causal only orders operations that depend on each other; eventual only promises that, if writes stop, replicas converge. CAP-C means the top rung. (And none of this is the C in ACID, which is about transactions preserving declared invariants — an ACID database can still serve stale, non-linearizable reads across replicas.)

Don't confuse linearizability with serializability

The other "strong" guarantee people reach for is serializability, and it is a different axis from CAP-C. Keep them apart:

• Linearizability (CAP-C) is about one object and real time: once a write is acknowledged, every later read — measured on the wall clock — must see it (or a newer value). It says nothing about transactions.
• Serializability is a transaction-isolation property about many objects: concurrent multi-object transactions must appear to execute in some serial order. It says nothing about real time, so a serializable database is free to pick a serial order that corresponds to a slightly stale snapshot.

They are orthogonal — you can have either without the other. PostgreSQL's SERIALIZABLE (serializable snapshot isolation, SSI) is the cleanest witness: every transaction reads from a consistent snapshot taken when it began, so a transaction can commit having read state that predates a write that had already committed in real time — a legal serial order exists, but it does not respect the wall clock. Serializable, not linearizable, and no replica is even involved. (Separately, reads on an async replica are not linearizable for the plainer reason that the replica lags — but don't fuse the two into one example: PostgreSQL refuses SERIALIZABLE on a hot-standby replica outright and raises an error, capping standby queries at REPEATABLE READ.) Conversely a single-object linearizable register (etcd, ZooKeeper) has no multi-object transactions to serialize at all. Combining both — every transaction serial and respecting real-time order — is strict serializability, the guarantee Google Spanner provides (via TrueTime). Interviewers love the follow-up "linearizable vs serializable — can you have one without the other?"; the answer is yes, and strict serializability is their union.

A traced example: judging a real operation history

Linearizability is checked, not asserted. You take the log of overlapping operations on a register x (initial value 0) and ask: does there exist one point-in-time for each operation, inside its own call–return window, that makes all reads correct? Two histories, same three clients:

Verdict: linearizable. Place the write's effect at t≈4. B (t2–t3) is entirely before that point, so reading 0 is legal; C (t6–t7) is entirely after, so it must — and does — read 1. One consistent story exists.

Now change only C's return value in a history where B reads after the write completes:

Verdict: NOT linearizable. Once B observed 1 (and the write had already completed), value 0 is gone forever; a later read returning 0 means the register went backwards in time. No single instant explains it. This is the exact failure a strongly-consistent store must prevent — and the reason it may have to block or error under a partition.

Availability (A): every live node answers, in bounded time

The mechanism: every request sent to a non-crashed node returns a non-error response within a bounded time — it may be stale, but the node never hangs and never says "try again later." That is a stricter, more theoretical bar than the operational "availability" on a status page.

The trap is conflating CAP-A with an SLA of nines. They are different axes. A CP store like etcd can post 99.99% annual uptime and still have zero CAP-availability the moment a partition isolates it, because by design the minority side returns errors. Conversely, the "bounded time" clause means a node that takes 30 seconds to answer is, for practical purposes, unavailable even though it never errored. High uptime does not imply CAP-A, and CAP-A does not require perfect uptime — it requires never withholding an answer from a working node.

Partition tolerance (P): surviving lost messages between live nodes

The mechanism: the system keeps operating when messages between nodes are dropped or arbitrarily delayed, splitting the cluster into groups that cannot communicate. Note what a partition is not: it is not a node crashing (that is just reduced capacity) — it is two live nodes that can no longer hear each other. That definition is broader than most engineers assume: a one-way (asymmetric) link where N1 hears N2 but not vice-versa is a partition; a GC pause or a saturated NIC that stalls heartbeats past their timeout is, to the rest of the cluster, indistinguishable from a cut cable.

This is why P is not a choice. Take nodes in New York and London: no vendor sells a transatlantic link that never drops a packet, and even a single missed heartbeat window is a partition. You cannot design partitions away; you can only decide what each side does during one. So on any real multi-node network P is mandatory, and the genuine dial is how strong a C you can afford to keep while still tolerating it.

Pitfalls

• "Eventual consistency" with no convergence bound. Eventual only promises replicas agree if writes stop — which they never do. Without an explicit staleness bound or anti-entropy schedule, "eventual" can mean minutes, and monotonic-read violations (a value that appears, then disappears on the next read) are legal. Demand a bound, not the word.
• Counting a slow node as available. CAP-A requires a bounded-time response. A node stuck behind a 40-second lock or GC pause satisfies neither A (too slow) nor its peers' view of P (looks partitioned). Latency is a correctness property here, not just a metric.
• Reading CAP-C as ACID-C. A fully ACID database with async read replicas is an AP-flavored system for those replicas — transactions preserve invariants on the primary while replicas still serve stale, non-linearizable reads. Interviewers probe exactly this gap.
• Assuming a partition means "the datacenter link went down." Asymmetric links, overloaded NICs, and long TCP timeouts partition far more often than cable cuts, so the C-or-A decision fires more frequently than teams plan for.
• Believing strong consistency is free when the network is healthy. CAP is silent on the no-partition case, but linearizability still costs a cross-node round trip per operation even then — the latency price PACELC's "else" branch makes explicit.

When to use it / how strong a consistency do you need

Because P is forced and A is often non-negotiable for user-facing systems, the component you most actively tune is the strength of C. Pick the weakest rung that still makes your invariant safe — stronger costs coordination, latency, and availability under partition.

• Linearizable (strong) — choose when a stale or reordered read is dangerous: balances, inventory decrements, unique-username reservation, distributed locks, leader election. What you gain: reads always see the latest committed write; you can reason as if there is one copy. What it costs: every operation coordinates (a round trip / quorum), so higher latency, and under CAP this is the rung that must sacrifice availability during a partition. Systems: etcd, ZooKeeper, Spanner's write path.
• Causal — choose when cause-and-effect ordering must hold but unrelated operations can float: comment threads (a reply never appears before the message it answers), collaborative editing. What you gain: it is provably the strongest model that stays fully available under partitions, and it is far cheaper than linearizable. What it costs: concurrent, unrelated writes may be observed in different orders on different replicas; you must track dependency metadata. Systems: MongoDB causally-consistent sessions, COPS.
• Eventual — choose when staleness is harmless and uptime/latency is everything: view counts, feeds, DNS, product catalogs, session stores. What you gain: maximum availability and lowest latency, writes never block. What it costs: stale and out-of-order reads, plus conflict resolution (last-write-wins can silently drop data; CRDTs fix that at the price of extra machinery). Systems: Cassandra, DynamoDB, Riak, DNS.

Crisp rule: use linearizable only for the handful of operations where a wrong-order read corrupts state; drop to causal when you just need effects to follow their causes while staying available; and use eventual for the majority of reads where a few seconds of staleness is invisible to the user.

Takeaways

• Each CAP letter is a testable guarantee: C = linearizability (a valid single-instant story for every read), A = every live node answers in bounded time, P = the cluster survives lost messages between live nodes.
• Consistency is a ladder (linearizable > sequential > causal > eventual), not a switch — the engineering skill is choosing the weakest rung that keeps your invariant safe.
• CAP-A is not an uptime SLA and not ACID-C: a CP system can boast four nines yet return errors under partition, and an ACID database can still serve non-linearizable replica reads.
• P is a hazard, not a menu item — asymmetric links, GC pauses, and timeouts all count as partitions, so the real choice is always the strength of C you can hold onto.

Re-authored and deepened for this guide. Sources: M. Herlihy & J. Wing, "Linearizability: A Correctness Condition for Concurrent Objects" (ACM TOPLAS, 1990); S. Gilbert & N. Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services" (2002); E. Brewer, "CAP Twelve Years Later" (IEEE Computer, 2012); L. Lamport on sequential consistency (1979); Ahamad et al., "Causal Memory" (1995); Lloyd et al., "Don't Settle for Eventual" (COPS, SOSP 2011); P. Viotti & M. Vukolić, "Consistency in Non-Transactional Distributed Storage Systems" (ACM Computing Surveys, 2016).