A Critique of the CAP Theorem

The CAP theorem says a replicated system cannot be consistent, available and partition-tolerant at once. Its popular form, "pick two", became a design slogan, and databases are often labeled CP or AP. Kleppmann argues that the slogan and the theorem both decide less than people think.

The terms are slippery. Consistency in CAP means linearizability, one specific strong model (every read sees the latest completed write), which is different from the C in ACID and from many weaker models in use. Availability, in Gilbert and Lynch's formal version, means every request to a non-failed node eventually gets a response, with no time limit, and even a node completely cut off must respond. By that definition, a system with an elected leader is "unavailable" even if its uptime in practice is very high, and a system that fails completely in a partition can count as available because all its nodes failed. Partition tolerance is not a feature at all; it is an assumption that partitions can happen, which every real network must make. Many practical systems end up neither CAP-consistent nor CAP-available.

The formal proof has gaps too. It only works if partitions can last forever, and in that model eventual consistency is impossible as well, so the theorem as stated does not separate strongly and eventually consistent systems. The CP versus AP division also hides a spectrum of models in between.

In place of CAP, Kleppmann proposes delay sensitivity. Model faults as network delay: a lost packet that is resent looks like extra delay, and a partition is a very long delay. Then ask, for each operation, whether its latency must grow with the delay d. Known lower bounds answer this: linearizable reads and writes are O(d); sequential consistency requires the read and write latencies to sum to at least d, so one can be O(1); causal consistency is the strongest model where both are O(1). An O(1) operation keeps working during a partition, at the cost that replicas converge later. Where the delay comes from also matters: a leader-based system waits on the leader, while a majority quorum waits only for the fastest majority.

Replace "CP or AP?" with "which operations can wait?" For each operation in a customer's system (placing an order, reading a balance, updating a profile, writing an agent's memory), decide whether it must reflect the latest write everywhere, which means it will wait on the network, or whether it can be served locally and converge later. That is a design decision you can make and test.

Availability means latency in practice. A response after a minute is a failure to a user. Define availability with a timeout in the SLO, then check which operations can meet it during a regional network problem.

Leaders are a latency risk during faults. In our simulation, when the client could not reach the leader, p99 write latency rose to 9.5 seconds while a majority quorum stayed at 19 ms. Know where a customer's database leader sits and what happens to writes when the path to it degrades.

Local reads are fast and sometimes stale. In our model, a read in another region 100 ms after a write missed it 12.7% of the time. For dashboards and recommendations that is fine; for balances and permissions it is not.

This applies to AI systems too. Vector indexes, caches, agent memory and feature stores are replicated data. Decide per use whether a stale embedding or memory is acceptable, and design for read-your-writes where users expect to see what they just did.