CAP, ACID, BASE, PACELC

Vocabulary for talking about distributed-system trade-offs.

CAP

Pick two of three when a network partition occurs:

• Consistency — every read sees the most recent write (linearizability).
• Availability — every request gets a non-error response.
• Partition tolerance — system keeps working when network drops messages between nodes.

The trick: P isn’t really optional. Networks partition. So in practice:

• CP system — under partition, refuses requests on the minority side to keep consistency. (Postgres single-primary, Spanner, ZooKeeper, etcd, MongoDB with majority writes.)
• AP system — under partition, both sides keep accepting requests; reconciles later. (Cassandra default, DynamoDB, Riak, CouchDB.)

CA (no partition tolerance) means “single machine” — not really distributed.

What CAP isn’t

• It’s not a steady-state choice. When the network is healthy, CP systems are also available. The trade-off only fires under partition.
• It’s not a binary. Real systems offer tunable consistency: e.g., Cassandra QUORUM reads from a majority of replicas (more consistent), ONE from any (more available).

PACELC — the missing piece

CAP only describes partition behavior. PACELC adds: even when there’s no Partition, you choose between Latency and Consistency.

If Partition: choose Availability or Consistency. Else: choose Latency or Consistency.

Most distributed systems trade some consistency for latency in normal operation: replicating async (low write latency, stale reads possible) vs sync (high latency, fresh reads). Cassandra is PA/EL by default; Spanner is PC/EC.

ACID vs BASE

ACID (transactional databases):

• Atomicity, Consistency, Isolation, Durability.
• Strong guarantees, lower throughput in distributed settings.

BASE (eventually-consistent stores):

• Basically Available
• Soft state — state can change without input
• Eventually consistent — given no new updates, all replicas converge

BASE was coined as a deliberate antonym to ACID by Eric Brewer’s group. The point: when scale forces you to give up ACID, name what you actually have.

Examples

Eventual consistency in practice

In an AP system, reads can be stale. To bound the staleness:

• Read repair — when a read sees inconsistent replicas, reconcile in the background.
• Hinted handoff — node A is down; node B holds writes destined for A and replays when A recovers.
• Anti-entropy — periodic background gossip to reconcile divergent replicas (Merkle trees in Cassandra).
• Vector clocks — track causality so concurrent updates can be detected (Riak).
• CRDTs — data types that mathematically converge (counters, sets) without coordination.
• Last-write-wins — simplest, but loses concurrent updates.

Linearizability vs serializability

Two different “strong consistency” guarantees often conflated:

• Linearizability — single-object: every read returns the most recent write, in real-time order.
• Serializability — multi-object: result of concurrent transactions equals some serial order (not necessarily real-time).
• Strict serializability — both. What ACID + linearizable gives you. What Spanner provides.

A system can be serializable without being linearizable (PostgreSQL serializable mode does not guarantee real-time ordering across separate transactions). And linearizable without being serializable (single-key linearizable KV store).

Choosing your model

Cheat-sheet for “what consistency do I need”:

Most apps need strong consistency for some data, eventual consistency for the rest. Putting everything in a single CP store is overkill; putting everything in AP is asking for incidents.

Interview angle

• Q: “What is CAP and which two should you pick?” — partition tolerance is non-negotiable; the real choice is CP vs AP under partition.
• Q: “Difference between ACID and BASE?” — strong vs eventual.
• Follow-up: “What’s PACELC and why was it needed?” — CAP only describes partition behavior; PACELC adds the latency/consistency trade-off in steady state.
• Follow-up: “Linearizable vs serializable?” — single-object real-time vs multi-object equivalent-to-serial.

See 08_transactions_isolation.md for ACID isolation in single-DB context, 14_sharding_partitioning.md for distributed implications.