Concept lesson · Foundations
CAP theorem: consistency, availability, and partition tolerance
Start here
Definition
The CAP theorem states that a distributed read/write system cannot guarantee both consistency (C) and availability (A) when a network partition (P) prevents replicas (copies of the same data) from communicating. C means linearizability: after a write completes, a later read must return that value or a newer write, as if there were one up-to-date copy. A means every request to a nonfailed participant eventually completes according to the operation’s contract.
Why it matters: Replicas may be alive but unable to exchange updates. We must decide whether an affected operation waits or fails to preserve one current history, or completes using potentially stale or conflicting state.
C is linearizability, A is a successful contract-compliant response from every non-failing node, and P means the model allows broken links. During a partition, the system cannot guarantee both C and A.
Read the diagram step by step
- C: reads respect one real-time order of completed operations.
- A: every request to a non-failing node eventually receives a successful response under the operation contract; this is not an uptime percentage.
- P: replicas may be unable to communicate.
- CP preserves linearizability by rejecting or waiting on some partitioned requests. AP continues responding but may return conflicting or stale values.
- CA is possible only when partition failures are excluded from the model; partition tolerance is not a feature to switch off in a network that can split.
Worked example
East and West both store seat S7 as free. The network splits. East confirms client A’s reservation. A later read at West must learn that change to return a current answer; returning “free” breaks C, while waiting indefinitely or refusing the read sacrifices A.
Key takeaways
- During a partition, C and A cannot both be guaranteed for the same read/write contract.
- CP preserves one history but some operations cannot complete; AP permits completion with weaker consistency.
- The triangle is a mnemonic. “Pick any two” hides that partitions are a failure condition, not an optional product feature.
You will learn to
- State the CAP theorem, define C/A/P, and explain the CP/AP/CA edges of the triangle.
- Use a completed-write/remote-read timeline to show why both guarantees cannot always hold.
- Choose partition behavior per operation without confusing CAP consistency with business rules.
Practice in this chapter
8 interview questions with model answers and follow-ups.
Go to interview practiceUseful foundations: Replication and durability · Databases, data models, and ACID transactions
Workload and timing examples are interview assumptions.
Dotted concept links open the relevant explanation in a new tab.
01What is the CAP theorem?
The CAP theorem: when a network partition separates replicas of a distributed read/write system, the system cannot guarantee both consistency and availability for every operation. It must allow some operations to remain incomplete, or allow results that do not fit one current, real-time-ordered history.
| Letter | Canonical meaning | Plain-language test |
|---|---|---|
| C: Consistency | Linearizability: clients observe one up-to-date copy | After a write completes, a read that starts later returns that write or a newer write; overlapping operations must still fit one valid real-time order |
| A: Availability | Every request received by a nonfailed participant eventually completes according to the operation contract | An isolated but live node must still complete reads/writes; returning a generic failure does not fulfill that guarantee |
| P: Partition tolerance | The model permits messages between groups of live nodes to be lost | Both sides may be alive and serving clients while they cannot exchange updates |
The familiar CAP triangle names the three properties. Its CP and AP edges describe different promises during a partition. The CA edge applies when partitions are excluded from the guarantee; it is not a way to wish away network failures. “Pick any two” is a memory aid that needs this qualification.
Use a single replicated object to test the guarantees. Seat S7 starts as Seat(S7, owner = null). Reservation is an atomic check-and-set of the owner, preventing two successful allocations from independent reads of null. This business invariant is distinct from the freshness promised by a read.
In the example history, client A’s reservation completes at 10:00:02 and client B starts a read at 10:00:03. A linearizable read must return client A as owner. Replication introduces an information gap: after communication fails, East can know the completed reservation while West retains the old free value. The following sections derive C, A, and P from that gap.
02C = consistency: linearizability and real-time order
CAP consistency means clients observe one up-to-date copy of the data. After a write completes, any read that starts later must return that value or the result of a newer write. This guarantee is called linearizability. If the system cannot provide a valid result, it may wait or refuse the operation to preserve consistency; that sacrifices availability for the affected request.
Linearizability requires an order compatible with real-time precedence of non-overlapping operations. It does not mean that every replica changes at the same physical instant.
Remember: A completed write constrains a later read.
Read the diagram
- Client A to Register: WRITE x = 1
- Register to Client A: SUCCESS: write completed
- Client B to Register: Only now: READ x
- Register to Client B: RETURN 1 (no intervening write)
The familiar phrase “all clients see the same data” describes this single-copy view. A simple test is to finish one write and then read from different clients, with no intervening writes: every successful read must agree with that write. It does not require every physical replica to update at the same instant.
| Step | Operation on seat S7 | What CAP consistency requires |
|---|---|---|
| 1 | East confirms client A’s reservation | The write has completed |
| 2 | Client B then reads through West | Return client A as owner, assuming no later change |
| 3 | West is isolated and only knows the old free value | Do not return “free” as a successful current read; coordinate, wait or refuse |
The formal definition says the same thing more precisely: each operation appears to take effect at one instant between its start and finish, and all operations fit one legal order that respects completed-before-started relationships. A read overlapping an unfinished reservation may see the earlier or later state, provided the whole history fits that order. This handles concurrency that the word “latest” alone leaves ambiguous.
03A = availability: every nonfailed participant can complete requests
CAP availability asks whether every request reaching a nonfailed participant completes according to the object’s operation contract, even in the allowed failure scenarios. For our read, the client receives an owner value. Refusing every read with “cannot contact East” does not meet that availability promise.
A legitimate business rejection is different. An authoritative reservation operation can answer “already reserved” when that is its valid result. An infrastructure refusal says that the service cannot establish or perform the operation at all.
04P = partition tolerance: live nodes cannot exchange messages
A network partition separates communicating participants. At 10:00:01, the link between East and West stops carrying messages. East still has power and serves client A; West still has power and serves client B. Neither side can reliably learn what the other side is doing.
A partition can come from a routing fault, a firewall mistake, or a failed network path. A machine crash is different, although a disconnected machine can look crashed to a failure detector. Missing replies reveal uncertainty; they do not prove the remote machine stopped accepting work.
“Partition tolerance” means our failure model permits this communication loss and our design states what remains guaranteed. It does not mean replication can magically cross the broken link. We cannot remove this possibility from a multi-location design merely by choosing a different database label. More independent links can lower the risk, but the question remains: what does each operation do when the messages still cannot arrive?
05Worked example: a partition between two seat replicas
Assume both copies initially contain the same record. The following trace deliberately lets East complete a local write while disconnected; it is a thought experiment that exposes the conflict.
The read starts after A has confirmed x = 1. There is no later write. The broken link prevents B from learning that value.
Remember: B can refuse or wait, or return stale data; it cannot guarantee both CAP properties here.
Read the diagram
- Trace a read at an isolated replica after a completed write elsewhere.
- A holds x = 1; B still holds x = 0.
- Waiting or refusing avoids a stale successful read but sacrifices CAP availability.
- Returning 0 completes the read but violates linearizability for this history.
Try from memoryWhy is returning 0 a consistency violation in this history?
The read begins after the write of 1 completes, with no intervening write. Linearizability therefore requires 1.
| Time | East and client A | West and client B |
|---|---|---|
| 10:00:00 | S7 is available | S7 is available |
| 10:00:01 | Messages to West stop | Messages from East stop |
| 10:00:02 | Store owner = client A; return success | Still holds owner = null |
| 10:00:03 | client A’s write has completed | client B asks for S7’s owner |
West has three plausible responses. Returning null completes a read but violates linearizability in this history. Waiting until it can discover the update preserves the possibility of a correct answer, but an indefinitely partitioned request does not complete. Returning “unavailable” is an explicit refusal of the read.
Guessing “client A” cannot solve the problem: West would have identical local evidence if nobody had reserved S7 or if another client had. It needs information that the partition prevents from arriving. This is the practical intuition behind CAP, rather than a rule to attach two letters permanently to every product.
- 1 → 210:00:02 reserve; success returnedClient A: reserve S7 → East: S7 = client A
- 2 → 3replication message cannot crossEast: S7 = client A → Broken East–West link
- 3 → 4West receives no updateBroken East–West link → West: S7 = available
- 5 → 410:00:03 read beginsClient B: read S7 → West: S7 = available
06CP, AP, and CA: interpret the triangle and choose per operation
The seat trace leaves a concrete choice: preserve the current-owner contract by withholding an answer, or keep answering while allowing older information. CP and AP are names for those different guarantees when partitions are permitted. CA describes a different assumption that excludes partitions from the executions being guaranteed.
| Triangle edge | Promise during a partition | Concrete behavior and cost |
|---|---|---|
| CP: consistency + partition tolerance | Preserve one valid real-time-ordered history; give up completing every request | A side unable to establish authority waits or rejects affected operations. A valid majority may continue, but a disconnected minority cannot promise success |
| AP: availability + partition tolerance | Complete operations at nonfailed participants; relax linearizability | West can return its last known seat map. If both sides accept writes, define the conflict semantics and reconcile later; this cannot safely promise the same exclusive seat to two buyers |
| CA: consistency + availability, excluding partitions | Both are possible when communication assumptions exclude partition executions | A single authority or connected replicas can provide both within the assumed model. Once isolated replicas must independently answer, the CAP tradeoff returns |
For this booking service, choose a single safe reservation authority backed by a replication/election protocol. When a participant cannot establish the authority required to change S7, it declines that change. With only two voters requiring both, a partition can stop new reservations entirely; a properly designed three-voter majority can let the connected majority proceed while the minority refuses writes.
The cost is lost purchasing availability for some customers during a fault. We accept it because promising the same seat twice would break the product. This is a design choice for the reservation operation, not a claim that every endpoint must stop.
| Operation | Chosen partition behavior | User-visible cost |
|---|---|---|
| Reserve S7 | Require the authoritative conditional change | Some attempts receive a retryable refusal |
| Display seating map | Permit a labeled cached view | Seat inventory display may be stale |
| Read confirmed order | Read an authority or verified session position | May wait or fail when authority is unreachable |
The seating map helps users choose a seat, but only a successful reservation confirms that the seat has been assigned to them.
07After the partition: recovery and conflict handling
At 10:00:20, communication returns. Before West promises current reads or accepts new reservations, it must recover the committed state and follow the protocol that decides which node may serve those operations. Replicas catch up or reconcile according to their protocol. An old leader must not keep committing conflicting updates merely because it resumed responding; ownership enforcement belongs to the replication design.
Client B retries a purchase using the same request identifier. If an earlier attempt committed but its response was lost, the service should retrieve that outcome rather than create a second operation. If it never committed, the authority can process it and report that client A already owns S7.
A product that deliberately accepted conflicting writes needs a separate merge or compensation policy. “Eventually consistent” does not tell us whether client A or client B receives the seat, and restoring communication does not undo promises already made to clients. For guarantees such as read-your-writes and causal ordering, continue with the consistency models chapter; they answer additional questions beyond CAP’s limit.
08Interview answer: explain CAP, then apply it
Interviewer: “How should a multi-region service choose consistency and availability?”
Candidate: “The CAP theorem says a distributed read/write system cannot guarantee both linearizability and completion of every request to a nonfailed participant when replicas cannot communicate. C means later reads see a completed write or a newer write, with operations fitting one valid real-time order; A is completion under the operation’s contract; P is the allowed loss of communication between live participants. The tradeoff concerns affected operations during a partition.
“I choose the guarantee for each operation. Reserving a seat requires one atomic decision by the service allowed to allocate it; a server unable to reach that service must wait or refuse. The seat display can show older data if the product allows it. During a partition, reservations may stop while the display remains usable.
“For a concrete test, a write completes in East before a read starts in isolated West. West cannot infer the write from its old local state. Returning the old value breaks linearizability; waiting indefinitely or refusing sacrifices availability. I would then specify replica placement, quorum and election rules, fencing, and retry handling. The label CP alone supplies none of those mechanisms.”
First explain CAP, then choose what each operation must guarantee and what that choice costs. Preventing two sales of one seat still requires an atomic allocation step. CAP explains which distributed guarantees can conflict; it does not implement that step.
Practise the interview questions
Say your answer aloud before opening the model answer. Then answer the follow-up and compare the reasoning.
What is the CAP theorem? Define C, A, and P, and explain the triangle with a concrete example.
Reveal a model answer
CAP says a distributed read/write system cannot guarantee both linearizable consistency and completion of every request to a nonfailed participant when network partitions are allowed. C means clients observe one up-to-date copy: after a write completes, a later read must return it or a newer write. Formally, operations fit one valid history respecting real-time order. A means every such request eventually completes according to its contract. P means live replicas can be unable to exchange messages.
Draw C, A, and P at the triangle's vertices. Label CP as preserving one history while some operations wait or fail, AP as permitting completion with weaker consistency, and CA as requiring that partitions are excluded from the guarantee. Do not present P as a network failure you can disable in production.
For example, East and West both store S7 as free. They lose contact. East confirms client A's reservation. A later West read cannot learn that fact: returning free violates C; refusing or waiting without completion gives up A. The design should state which behavior is acceptable for that operation.
Interviewer follow-up
Why is “every replica has the same data at every instant” an inaccurate definition of CAP consistency?
Reveal the follow-up answer
Linearizability constrains observable operations, not instantaneous physical equality of every copy. A follower can lag if the system routes, waits for, or validates reads so completed operations still fit one legal real-time order. A read overlapping a write may legally appear before or after it. But if the write completed before the read began, an older value is invalid in the absence of an intervening write. The physical replication and the visible consistency promise are different levels.
What the answer must demonstrate: State the theorem before the caveats; define all three letters and use one completed-write/later-read partition trace.
Why does a quick 503 not prove CAP availability?
Reveal a model answer
“The client reached a working participant but did not complete the requested seat read. The server replied quickly, which is useful operationally, but refused the object operation. I would count that separately from a valid ‘already reserved’ result and separately from the product’s latency target.”
Interviewer follow-up
Does returning ‘already reserved’ sacrifice availability?
Reveal the follow-up answer
“Not when that is a valid result established by the reservation operation. It reports a business outcome. Inventing that result without authority just to avoid an error would violate the operation’s contract.”
What the answer must demonstrate: Separate infrastructure failure from legitimate business rejection.
Can a partition happen while both databases are healthy?
Reveal a model answer
“Yes. East and West may both run normally and answer their local clients while network messages between them are dropped. That is why checking each process’s health is insufficient. I need to know which communication and authority assumptions an operation requires.”
Interviewer follow-up
Would a second network link solve CAP?
Reveal the follow-up answer
“It reduces the chance of losing communication, but cannot prove communication will always work. I still define behavior for the residual case where every usable path fails.”
What the answer must demonstrate: A network partition is not necessarily a server crash.
East and West start with S7 free, then become partitioned. East confirms a reservation at 10:00:02; a West read begins at 10:00:03. Why can West not guarantee a linearizable answer while completing every such read?
Reveal a model answer
“West has the same local state in several possible histories: client A reserved in East, someone else reserved, or nobody wrote. No East message has arrived. Its old null value cannot distinguish them. Answering immediately may choose the wrong history; waiting for information can prevent completion during a continuing partition.”
Interviewer follow-up
Could synchronized clocks reveal the missing write?
Reveal the follow-up answer
“Clocks can tell West that time passed, but not who wrote or whether a write happened. Timing assumptions may support particular protocols, but time alone does not carry the missing data.”
What the answer must demonstrate: Explain the missing information, not just repeat ‘choose two.’
How would you handle the last seat during a partition?
Reveal a model answer
“I would allow only the participant with valid write authority to perform the atomic available-to-reserved transition. A disconnected minority would decline it. That may stop some purchases, but a successful confirmation then means the seat was reserved by the node currently authorized to make that decision. I would specify the quorum and safe leader change rather than relying on a product label.”
Interviewer follow-up
What if we have exactly two replicas?
Reveal the follow-up answer
“If safe progress requires both, a split leaves neither side able to complete new writes. I would discuss a third voting participant and failure-domain placement, or accept the two-node availability cost.”
What the answer must demonstrate: Adding replicas is not the same as defining a safe election protocol.
Does preventing double sales imply every read is CAP-consistent?
Reveal a model answer
“No. I can send all reservations through one atomic authority while serving a stale seating map elsewhere. The business invariant can hold even when that display is not linearizable. Conversely, a correctly ordered store can still oversell if my application uses an unsafe read-then-write algorithm.”
Interviewer follow-up
How would you fix that unsafe algorithm?
Reveal the follow-up answer
“Make checking availability and assigning the owner one protected operation, using a conditional update or suitable transaction. Read freshness alone does not make two separate operations atomic.”
What the answer must demonstrate: CAP C and application invariants are related design concerns, not identical definitions.
A reservation request times out without a known outcome. How should the client retry?
Reveal a model answer
“Reuse the operation identifier and ask the authority for the durable outcome. A timeout means the response was not received; it does not prove the reservation failed. If the old attempt committed, return that result. If it did not, process the retry under the same ownership rules.”
Interviewer follow-up
Should West create a new reservation while East is unreachable?
Reveal the follow-up answer
“Only if West can safely take responsibility for the reservation. If East may already have reserved the seat, creating an unrelated reservation at West could create two conflicting bookings.”
What the answer must demonstrate: A missing response is an unknown outcome.
What must happen after the partition heals?
Reveal a model answer
“Replicas must converge on the protocol’s authoritative history, and obsolete writers must remain fenced. I would verify catch-up before routing reads that promise current state. If our policy allowed conflicting writes, I also need an explicit business repair policy; network recovery alone cannot choose who deserves a promised seat.”
Interviewer follow-up
Can the whole site have one useful AP or CP label?
Reveal the follow-up answer
“Only as shorthand for a specified operation and failure model. A stale advisory map and an authoritative reservation already make different choices. AP also does not define eventual convergence or conflict resolution; I must explain how accepted updates propagate and reconcile after communication returns.”
What the answer must demonstrate: Recovery must honor promises made before and during the fault.
Blank-page exercise · 12 minutes
Build the answer yourself
Draw and label the CAP triangle, explaining the assumption behind CA. Then draw East and West storing S7. Show a partition, client A’s completed reservation in East, and client B’s later read at West. Design separate browsing and purchasing contracts.
- Define C, A, and P before choosing a design, and explain why the triangle does not mean partitions can be switched off.
- Show exactly which information West lacks at client B’s read.
- State one operation allowed and one refused during the partition, with the user cost.
- Explain safe catch-up and the outcome of an ambiguous retry.
Check that each component and design decision follows from your requirements and workload.
Recall the key ideas
Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.
CAP theorem: consistency, availability, and partition toleranceState CAP and label the triangle.Recall first, then reveal
The CAP theorem states that a distributed read/write system cannot guarantee both consistency (C) and availability (A) when a network partition (P) prevents replicas from communicating. C means linearizability: after a write completes, a later read must return that value or a newer write, as if there were one up-to-date copy. A means every request to a nonfailed participant eventually completes according to the operation’s contract.
Partition present: preserve one history (CP) or complete with weaker consistency (AP). CA excludes the partition case.
Return to lessonCAP theorem: consistency, availability, and partition toleranceBoth replicas are running but cannot exchange messages. Which CAP letter describes this?Recall first, then reveal
P: a network partition. Machines can be alive and serve their local clients while communication between them is lost.
Live participants; unavailable communication.
Return to lessonCAP theorem: consistency, availability, and partition toleranceCan returning “temporarily unavailable” preserve every CAP guarantee?Recall first, then reveal
It can protect an authoritative history, but it sacrifices availability for the refused operation. A quick error is not a successful read of the object.
Fast refusal is still refusal.
Return to lessonCAP theorem: consistency, availability, and partition toleranceDoes a stale seat display necessarily mean the seat can be sold twice?Recall first, then reveal
No. Display reads may be stale while reservations use one atomic authority. CAP read consistency and the no-double-sale business rule are different claims.
Displaying a seat and reserving it can require different consistency guarantees.
Return to lessonFinal revision
Summary and interview notes
CAP identifies a limit: when live replicas cannot communicate, a replicated read/write service cannot promise both linearizable answers and completion at every nonfailed participant. Choose the behavior per operation, then supply the replication, authority, retry, and recovery mechanisms that implement it.
Remember these points
- C means later reads see a completed write or a newer write; all operations fit one legal real-time order. Physical replicas need not update simultaneously.
- A concerns completing the specified operation at every nonfailed participant, not merely returning a fast error or meeting an uptime percentage.
- A CP-style operation may wait or refuse when it cannot confirm the current state or safely change it. An AP-style operation relaxes linearizability to keep responding during a partition.
- The CA edge excludes partition executions from its promise; it cannot disable network failures.
- An atomic reservation can prevent double sales even when an advisory seating display is stale.
Interview tips
- Explain the missing information with a completed East write followed by a West read during the partition.
- State what a valid response means before deciding whether a business rejection sacrifices availability.
- After choosing partition behavior, describe healing, obsolete writers, and retries with unknown outcomes.
Important qualifications
- The formal availability property has no fixed millisecond bound; product latency objectives are separate.
- AP does not automatically supply eventual convergence, and CAP consistency does not enforce application invariants by itself.
Technical references
- Gilbert and Lynch: Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web ServicesPrimary proof and definitions. The two-client seat trace is an original bounded example, not a production-system claim.
- Eric Brewer: CAP Twelve Years LaterThe originator explains why pick-two is too simple and why the partition decision and recovery must be explicit.
Practice marks stay in this browser.