Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

CAP theorem and BASE

Clear explanation of the CAP theorem (formal statement, assumptions, diagram to draw) and BASE (Basically Available, Soft state, Eventual consistency) with examples, common mistakes and exam guidance.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Distributed databases are used when data is stored on multiple machines (replicas or shards) for scalability and fault tolerance. Engineers use the CAP theorem to decide trade-offs (consistency vs availability) when designing replication, partitioning and failover; they use BASE principles when choosing relaxed consistency models (e.g., in NoSQL systems such as Cassandra or Dynamo) to get higher availability and scalability.

Key ideas

Start from first principles: a distributed database is a system where multiple machines (nodes) cooperate to store and serve data. Before using the terms, define them.

  • Node — a single machine or process that stores or serves data.
  • Client — an agent (user, application) that sends read/write requests to nodes.
  • Communication link — the network channel between nodes; it can fail or be slow.
  • Replica — a copy of a piece of data stored on one or more nodes.

Now the central theorem and related definitions:

  • Consistency (in CAP context) — here we mean linearizability (also called atomic consistency). Linearizability is the property that operations appear to occur instantaneously at some point between their invocation and response; equivalently, all clients see operations in a single global order consistent with real-time. Define this before using it: linearizability requires each read to return the value of the most recent completed write according to global real time order.

  • Availability (in CAP context) — every request received by a non-failing node must eventually result in a response (not necessarily the latest value), without assuming any fixed bound on time in an asynchronous network. That is, the system continues to accept and reply to client requests.

  • Partition tolerance — the system continues to operate despite arbitrary message loss between nodes (a network partition). Formally: the system must uphold its guarantees even if messages between some nodes are lost indefinitely.

  • CAP theorem (informal statement / Brewer's observation) — in a distributed system, in the presence of a network partition, a system must choose between consistency and availability.

  • CAP theorem (formal Gilbert–Lynch statement) — No asynchronous networked system (one that can have network partitions) can provide all three of (i) linearizability, (ii) availability, and (iii) partition tolerance. In other words, if partitions can occur, you cannot guarantee both availability and linearizability at the same time.

Assumptions behind the formal theorem: an asynchronous network model (no fixed bounds on message delays) and the possibility of arbitrary partitions (message loss between groups of nodes). Availability is defined per non-failing node: every request it receives must eventually get a response. The theorem is about worst-case guarantees under partitions.

Important clarifications students must remember (these are tested often):

  • CAP is about what happens during a network partition. If there are no partitions, you can have both consistency and availability.
  • CAP does not measure degrees of consistency or availability; it is about guarantees (yes/no) under the partition scenario.
  • Different authors use "consistency" differently. In databases courses, when CAP is discussed formally, use the linearizability definition.

Related practical idea (quorum rule): when data is replicated on N nodes and the system uses quorums, read–write quorums overlap if R + W > N, where R is the number of replicas that must respond to a read, and W is the number that must acknowledge a write. With a correct version ordering (e.g., a leader or monotonic logical timestamps) and reads that pick the highest-version value, this overlap can provide linearizable (strong) reads; the overlap alone does not guarantee strong consistency without such ordering/selection rules.

BASE (used for many NoSQL systems) definitions:

  • Basically Available — the system guarantees availability (it will respond) even if the result may not be the latest.
  • Soft state — the system state may change over time without new input, because replicas are still propagating updates (there may be in-flight changes).
  • Eventual Consistency — if no new updates are made, eventually all replicas will converge to the same value. Define eventual consistency precisely: given a finite number of updates and assuming communication eventually delivers messages, all nodes will converge to the same state in finite time.

Diagram to draw for an exam (exact description):

  • Draw two circles labeled Node A and Node B. Draw two clients: Client 1 connects to Node A, Client 2 connects to Node B. Draw a jagged (broken) network link between Node A and Node B and label it "partition". Draw an arrow from Client 1 to Node A labeled "write X=1" and an arrow from Client 2 to Node B labeled "read X?". This diagram is used to explain the CAP choice: if Node B must reply, it may return an old value (Availability over Consistency) or refuse/return error until it can contact Node A (Consistency over Availability).

Formulas

R + W > N — R = read quorum size (number of replicas that must respond to a read), W = write quorum size, N = total number of replicas. When this inequality holds, read and write quorums overlap, giving strong consistency for read-after-write.

Eventual consistency: lim_{t->∞} replica_state_i(t) = S, for all replicas i, assuming no further updates and reliable eventual delivery. (Interpretation: with no new writes and eventual message delivery, all replicas converge to the same final state S.)

CAP statement (informal): under partition(s), you must choose either C (linearizability) or A (availability). — not a numeric formula but a concise rule to remember.

Worked examples

Example 1 — Explain, with a diagram, why a two-node partition forces a trade-off. Model answer (exam style):

  1. Draw two nodes A and B, clients C1 and C2, and a broken link between A and B as described above.
  2. Suppose C1 writes X=1 to A. A accepts the write and replies (system is available). The write has not been propagated to B due to the partition.
  3. If C2 reads X from B and the system must remain available, B must return some value. If B returns old value X=0 then linearizability is violated (inconsistency). If B refuses to answer until it contacts A, availability is violated.
  4. Therefore, under partition, you must sacrifice either availability (make B refuse) or consistency (allow B to return stale value). This demonstrates the CAP trade-off. (End model answer.)

Example 2 — Numeric quorum selection for N=3 replicas. Question: N=3. Choose R and W to get strong consistency and also show an available configuration. Answer:

  1. To guarantee strong consistency, pick R and W so that R + W > 3. Common choice: W=2, R=2 gives R+W=4>3.
  2. Read path: contact any 2 replicas and return the latest timestamped value. Write path: require acknowledgements from any 2 replicas before committing.
  3. This ensures any read overlaps with the latest write on at least one replica, so reads see the latest committed write. This guarantee assumes a consistent version ordering (e.g., a leader or monotonic logical timestamps) and that reads choose the highest-version value; quorum overlap alone is not sufficient for linearizability.
  4. For higher availability at cost of consistency, choose W=1, R=1. Then R+W=2 ≤ 3, so reads/writes may not overlap and stale reads are possible during partitions, but each single node can respond quickly. (End model answer.)

Example 3 — BASE / eventual consistency scenario (model answer): Question: How does eventual consistency work in a key-value store after a write? Answer:

  1. Client writes key K=V1 to Replica A. A stores the update and responds (system is basically available).
  2. Replicas B and C will receive the update asynchronously (gossip, hinted handoff, or anti-entropy). Until they apply the update, reads to B/C may return older values (soft state).
  3. If no more updates happen, background replication will deliver the update to B and C; with conflict resolution (e.g., timestamps or vector clocks), all replicas will converge to value V1 (eventual consistency).
  4. If concurrent writes occur, conflict resolution rules (last-writer-wins, merge functions, or application-level resolution) decide the final converged state. (End model answer.)

Common mistakes

  • Using the word "consistency" without defining it — many meanings exist (ACID consistency vs linearizability vs serializability vs eventual consistency). Specify which one you mean.
  • Thinking CAP proves you cannot have consistency and availability ever — it only applies when partitions are possible.
  • Confusing eventual consistency with "inconsistent forever" — eventual consistency means convergence if updates stop and messages are delivered.
  • Forgetting to state assumptions of the theorem (asynchronous network and possible partitions).

For your exam

Typical question types:

  • Definitions: Define CAP theorem, define linearizability/availability/partition tolerance, define BASE and eventual consistency. Full marks: precise definitions, mention assumptions (partitions), explain the difference between CAP-consistency and database "ACID" consistency.
  • Short notes: Explain the implications of CAP for system design. Full marks: give examples (e.g., Dynamo/Cassandra choose availability and eventual consistency; traditional RDBMS often choose consistency and availability but sacrifice partition tolerance by stopping or returning errors on partition).
  • Derivation/diagram: Show with a two-node partition why you must choose C or A. Full marks: draw the partition diagram, show a write to one node, a read to the other, and explain the two outcomes.
  • Numericals/quorum: Given N, choose R and W to get strong consistency; show trade-offs. Full marks: use the formula R + W > N, give concrete numbers and explain latency/availability effects.
  • Long-answer comparative: Compare ACID transactions with BASE. Full marks: define ACID terms (refer to Transactions and ACID properties topic), explain when each approach is preferred, examples of systems.

Always state assumptions, define terms before using, and if asked about real systems give a brief example (Dynamo-style quorum, Cassandra tunable consistency, MongoDB replicas with primary/secondary / majority write concern) but do not re-teach replication protocols in detail.

Quick check

  1. What does the "P" in CAP stand for and what does it mean?
  2. State the quorum rule that guarantees strong consistency in replicated systems.
  3. Expand BASE and give one sentence describing "eventual consistency". Answers: 1. Partition tolerance — system continues to operate despite message loss between nodes. 2. R + W > N (R = read quorum, W = write quorum, N = replicas). 3. B: Basically Available, S: Soft state, E: Eventual consistency — eventually all replicas converge to the same value if no new updates occur.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?