CAP Theorem and Distributed Consistency
CAP is frequently reduced to “pick two of consistency, availability, and partition tolerance,” which produces weak interview answers. The theorem concerns an asynchronous distributed system during a network partition: it cannot guarantee both linearizable consistency and a response from every non-failing node for every request. Outside partitions, systems still trade latency, consistency, durability, and cost; within one product, different operations can make different choices. Senior candidates define terms, trace an execution, and state user-visible behavior rather than assigning databases simplistic labels.
How to use this chapter
- Read the mental model and mechanics without taking notes.
- Close the page and explain the topic aloud in five minutes.
- Work the quantitative example on paper.
- Answer the question ladder without revealing the answer signals.
- Complete one design drill and score yourself with the senior checklist.
Learning objectives
- Define CAP consistency, availability, and partition precisely enough to analyze an execution.
- Explain why network partitions force a choice for a particular operation, not a permanent product label.
- Distinguish linearizability from serializability, eventual, causal, and session guarantees.
- Use quorum and ownership examples without overstating what quorum arithmetic proves.
- Apply CAP to real APIs, caches, queues, leases, and multi-region workflows.
- Discuss PACELC-style normal-operation latency/consistency choices and recovery after partition healing.
Mental model
Imagine one logical register replicated on nodes A and B. A network partition prevents communication, but clients can still reach each side. A client writes x = 2 to A and gets success; another client then reads from B. If B must respond, it may return the old value because it cannot know A’s write—violating linearizability. If B refuses or waits indefinitely to preserve a single current value, the system is not available under CAP’s per-request definition. The theorem is about this indistinguishability, not about a database being generally “down.”
Core mechanics
Precise CAP terms
Consistency in CAP is commonly formalized as atomic/linearizable consistency: each operation appears to take effect at one instant between invocation and response, respecting real-time ordering. It is not merely “all replicas eventually match,” nor the C in ACID. Availability means every request received by a non-failing node eventually returns a non-error response, not “five nines over a month.” Partition tolerance means the system’s model includes lost or arbitrarily delayed messages between groups of nodes.
In real distributed deployments, communication failure is unavoidable enough that designers cannot assume it away. During partition, preserving linearizability may require a minority or uncertain node to reject/wait; preserving response availability may allow divergent operations. The theorem does not say only two properties can ever exist when the network is healthy.
Linearizability and serializability
Linearizability is a real-time property of operations on objects: once a write completes, later reads must observe it or a newer write. Serializability is a transaction isolation property: concurrent transactions behave like some serial order, but that order need not respect external real-time order unless the system provides strict serializability. A system can have serializable transactions on a stale replica and therefore not be linearizable globally.
Use the guarantee that matches the invariant. Leader leases and quorum/consensus reads can provide linearizable access; snapshots can provide consistent historical reads; causal consistency preserves happens-before relationships; read-your-writes and monotonic reads provide user/session comfort with less global coordination.
Operation-level choices
A system may be CP for metadata ownership changes, AP for telemetry ingest, and stale-tolerant for cached reads. Even one API can split behavior: GET serves a stale copy during isolation, while PUT username requires quorum and returns a retryable unavailable error. Labeling the whole product CP/AP obscures these contracts.
State whether errors, stale responses, tentative acceptance, queued local writes, and partial results are allowed. “Available” in business terms can include a graceful error page, but CAP’s formal availability excludes error responses; be clear which meaning you use.
Quorums, consensus, and ownership
Majority consensus groups can continue while a majority communicates; a minority rejects authoritative updates. This sacrifices CAP availability on the minority to preserve one log. Quorum-style replicated stores may accept/read subsets and reconcile versions, but R + W > N is not a universal proof of linearizability. Membership changes, concurrent writes, sloppy quorums, failed writes, stale configuration, and read-repair timing matter.
Single-writer ownership can localize coordination: a record has a home region or shard leader. During loss of that owner, the system can wait/fail, promote with a quorum and fence the old owner, or accept tentative/conflicting work elsewhere. Each is a CAP choice plus an operational policy.
Clocks do not remove partitions
Synchronized clocks can enable useful ordering bounds, leases, and globally distributed transaction protocols, but clocks have uncertainty and cannot communicate a write across a partition. Last-write-wins based on wall time can discard concurrent intent and behave badly under skew. Hybrid logical clocks and version vectors help reason about causality/concurrency, yet conflict semantics remain a domain decision.
Timeouts are failure suspicions, not proof. A node that cannot hear a leader cannot know whether the leader is dead or merely isolated. Terms, quorum, fencing tokens, and leases bounded by clock assumptions prevent two authorities from safely proceeding.
Partition detection and degraded modes
You cannot instantly and perfectly detect a partition. Systems infer trouble from missed heartbeats, failed RPCs, or quorum loss. Detection thresholds trade outage duration against false failover. Degraded behavior should be explicit: read-only mode, stale cache, queued local operation, partial result, home-region routing, or rejection with retry metadata.
Prevent retry storms by respecting deadlines and backoff. Do not allow every layer to retry independently. Surface consistency/freshness where useful—for example, “last synchronized at …” or a version token—so clients can make informed choices.
Healing and convergence
Restored connectivity does not automatically restore correctness. A single-log system catches up followers and may discard an uncommitted fork. Multi-writer systems exchange versions and merge or expose conflicts. Caches invalidate/expire stale entries; queues redeliver; directory maps converge under newer epochs. Deletes need durable markers long enough to prevent resurrection.
Define an anti-entropy/reconciliation process, rate limits, priority, and audit. Recovery traffic can overload the healthy system. Track divergence count, oldest unresolved conflict, replay lag, and data checksums—not only “all nodes green.”
PACELC and normal operation
CAP focuses on partition executions. When there is no partition, replicated systems still trade latency against consistency because coordination across replicas/regions takes time. PACELC summarizes: if Partition, choose Availability or Consistency; Else, choose Latency or Consistency. It is a heuristic taxonomy, not a replacement for a full operation contract.
A locally served stale read may take milliseconds, while a linearizable cross-region read/write needs at least wide-area communication or a clever ownership/lease arrangement. Quantify the latency path and decide which calls truly need global ordering.
Applying CAP to common components
DNS and caches often favor stale availability within TTL. Service discovery or shard ownership may favor consistency for writes but allow stale reads plus server redirects. A message queue can accept locally and later reconcile only if duplicate/order semantics are acceptable; a single ordered partition usually needs an authoritative quorum. Rate limiters may allow bounded overshoot through regional quotas instead of global coordination on every request.
For each component, ask: what is the object, what operation must be linearizable, which nodes can be partitioned, what response is permitted, and how is divergence repaired?
Decision table
| Decision | Prefer the first option when… | Prefer the second option when… | Senior caveat |
|---|---|---|---|
| Reject/wait vs accept conflicting work | The operation protects uniqueness, money, ownership, or an irreversible invariant. | The domain has safe merge, compensation, or bounded overshoot. | Return semantics must distinguish committed, tentative, queued, and rejected outcomes. |
| Linearizable vs session-consistent read | Decisions must observe the latest completed write globally. | A user needs own-write/monotonic behavior but cross-user freshness can lag. | Session tokens may need to cross devices or services; define fallback when a replica is behind. |
| Global consensus vs home ownership | Any region must mutate the same key with one global order. | Keys can be assigned to a region and remote calls are acceptable. | Ownership changes themselves require strongly coordinated metadata and fencing. |
| Serve stale cache vs fail closed | Content is low-risk and availability is more valuable than freshness. | Authorization, revocation, safety, or financial data cannot be stale past a bound. | Use explicit stale windows, version checks, and emergency invalidation where required. |
| Merge vs human conflict | Operations commute or a deterministic domain rule preserves intent. | Concurrent edits are semantically ambiguous or high value. | Do not hide data loss behind last-write-wins; retain versions/audit. |
| Synchronous cross-region vs asynchronous | RPO and one-copy ordering justify WAN latency and partition unavailability. | Local latency/availability is primary and lag/loss window is acceptable. | Hybrid per-operation or per-data-class policies are often appropriate. |
Quantitative reasoning
Failure modes and production signals
| Failure mode | What users see | Likely cause | Mitigation / design response | Useful signals |
|---|---|---|---|---|
| Minority accepts authoritative writes | Conflicting histories and possible data loss | No quorum/fencing or stale lease | Reject writes without authority, use terms/fencing, audit divergence | Simultaneous leaders, term mismatch, forked log |
| False failover | Brief latency becomes leadership churn | Aggressive timeout under load/network jitter | Adaptive detection, pre-vote/quorum, load isolation, stable leases | Election rate, heartbeat latency, leader tenure |
| Stale security decision | Revoked user/token remains accepted | AP cache/replica beyond safe freshness | Fail closed or short bound/version introspection, push invalidation | Decision data age, revocation propagation, stale hits |
| Conflict overwrite | User edit silently disappears | Last-write-wins on concurrent versions | Retain versions, domain merge, conflict UI, audit | Concurrent versions, merge outcomes, overwrite count |
| Recovery overload | System degrades when partition heals | Unbounded replay, anti-entropy, cache refill | Throttle/prioritize recovery, reserve resources, staged convergence | Replay/repair queue, network/disk, foreground p99 |
| Retry amplification | Duplicate writes and cascading overload | Ambiguous timeout plus retries at every layer | Idempotency keys, one retry owner, budgets/backoff, admission | Attempts/request, duplicate keys, timeout source |
| Delete resurrection | Removed data reappears after repair | Replica missed deletion and tombstone expired | Versioned tombstones, repair-before-GC, privacy erasure workflow | Old-version detections, tombstone age, repair coverage |
Senior-level lenses
CAP is an execution argument, not a product quadrant
Draw two replicas and a partition, then trace a write/read. Say which side answers and why. Apply the analysis to an operation. Different APIs and even read versus write on the same object may choose differently.
Business availability differs from formal availability
A checkout service returning “please retry” may meet an organizational graceful-degradation goal but is unavailable in CAP’s formal sense. Use both concepts carefully. Often the best product behavior is a controlled error rather than an inconsistent success.
Change the problem with escrow and ownership
Many global counters do not need a cross-region consensus call per event. Allocate regional quota, assign key ownership, reserve inventory, or use unique ID namespaces. These techniques preserve a bounded invariant while trading utilization/flexibility.
Recovery semantics are part of consistency
Accepting writes on both sides is not a complete AP design. Define version metadata, merge function, deterministic replay, audit, tombstones, and what users see when two irreversible actions conflict. Convergence must be measurable.
Consistency can be scoped and monotonic
A user often needs read-your-writes and monotonic state more than universal latest-value reads. Version tokens, sticky/home routing, and replica catch-up barriers can deliver useful semantics at lower cost. Do not overbuy global linearizability where session guarantees suffice.
Dependency CAP choices compose badly
An API can be available only if its authorization, configuration, discovery, database, queue, and KMS paths have compatible degraded modes. One fail-closed dependency can make an otherwise AP read path unavailable; one stale dependency can violate correctness. Analyze the full critical path.
Interview question ladder
State CAP without ‘pick two.’
Show strong-answer signals
During a network partition, a distributed system cannot guarantee both linearizable consistency and a non-error response from every non-failing node for every operation.
Is partition tolerance optional?
Show strong-answer signals
A single-node system can avoid distributed partitions, but once correctness depends on communicating nodes, message loss/delay must be handled; the choice is behavior during it.
Is ACID consistency the same as CAP consistency?
Show strong-answer signals
No. ACID C means transactions preserve application/database invariants; CAP C refers to atomic/linearizable visibility.
Why does a majority leader reject writes in the minority?
Show strong-answer signals
It cannot prove it remains the sole ordered authority; accepting could fork history. Rejection sacrifices formal availability to preserve consistency.
Can R + W > N guarantee strong consistency?
Show strong-answer signals
Not alone; discuss replica membership, versioning, concurrent writes, failed/sloppy quorums, read algorithm, and repair.
Give an AP-friendly operation.
Show strong-answer signals
Shopping-cart item additions or telemetry with unique event IDs can accept both sides and union/deduplicate, provided domain merge and later repair are defined.
Design behavior for a global username service during region partition.
Show strong-answer signals
Uniqueness needs authoritative quorum/home ownership or tentative reservation with possible rejection; describe API state, timeout, fencing, and reconciliation.
Should authorization cache serve stale data during control-plane failure?
Show strong-answer signals
Classify grants vs revocations, max staleness, fail-open/closed by action risk, signed expirations/version, emergency kill path, audit.
Design a globally distributed rate limiter.
Show strong-answer signals
Strong global counter versus regional token leases/escrow, bounded overshoot, allocation, expiry, partition behavior, hot keys, observability and abuse.
A multi-leader store healed but values differ. What now?
Show strong-answer signals
Identify concurrent versions, apply domain merge/operation replay, preserve audit, repair replicas/indexes, notify for irreconcilable conflict, throttle recovery.
Define consistency classes for a platform.
Show strong-answer signals
Named operation-level guarantees, permitted staleness/errors, client tokens, topology, SLOs, test harnesses, metrics, and examples for money/auth/content/analytics.
Review a proposal that labels every service CP or AP.
Show strong-answer signals
Replace labels with objects/operations, partition scope, responses, invariants, normal latency trade, recovery, dependencies, and migration assumptions.
Design drills
For profile reads, username changes, password revocation, cart edits, payment authorization, and analytics events, choose partition behavior and healing semantics.
What the interviewer is testing
Operation-level classification and business-risk reasoning.
Enforce a global API quota across 20 regions with low latency. Compare consensus, regional leases, approximate sketches, and post-facto billing.
What the interviewer is testing
Changing invariants to bound coordination cost.
Two regions accept offline edits to a shared document. Define causal metadata, merge granularity, conflict UI, history, and deletion behavior.
What the interviewer is testing
Convergence that preserves user intent.
Common weak answers and how to improve them
“A database can only have two of C, A, and P.”
Show the stronger answer
The forced trade-off is consistency versus formal availability during a partition; healthy operation has other choices.
“We choose partition tolerance.”
Show the stronger answer
Distributed systems must define partition behavior; say which operations reject, serve stale, or merge.
“Eventual consistency means replicas eventually agree.”
Show the stronger answer
Also define assumptions, conflict resolution, read guarantees, convergence time, and recovery load.
“Quorum equals strong consistency.”
Show the stronger answer
Describe the complete protocol and failure/membership assumptions.
“Availability means our uptime percentage.”
Show the stronger answer
Distinguish CAP’s response property from service SLO and graceful errors.