CAP PACELC and Consistency Models

CAP, Precisely Stated

Gilbert–Lynch CAP: when a network partition occurs, a distributed read/write store chooses between consistency (every read sees the latest committed write — linearizability in the proof) and availability (every non-crashed node answers, even if stale). Partition tolerance isn't optional — networks partition — so the real choice is CP vs AP during partitions.

The "pick 2" triangle misleads three ways, and interviewers reward candidates who say so:

1. Partitions are rare; latency is forever. Most of a system's life has no partition, and CAP says nothing about that period. A "CP" and "AP" system can behave identically with no partition.
2. Availability and consistency are not binary. Timeouts, 99.9% vs 99.99%, stale-by-100ms vs stale-by-minutes — the choice is a dial (how long do you wait before giving up and serving stale?) not a switch.
3. One system makes different choices per operation. Cassandra with QUORUM reads/writes is CP-ish per operation; with ONE it's AP — same cluster, dial turned per query (see Quorums for the R+W>N machinery).

The usable interview framing: "CAP governs behavior during partitions; my SLA numbers (timeout, retry, staleness bound) govern everything else."

PACELC: The Completion

PACELC (Abadi): if Partition, trade Availability vs Consistency; Else, trade Latency vs Consistency. The "else" clause is where systems actually live:

• ELC (else-latency-consistency): DynamoDB/Cassandra quorum reads pay cross-replica RTT for freshness; ONE reads return in single-digit ms but may be stale. Leader-based systems (see Single Leader Replication) route writes through the leader — one extra hop of latency buying a single serialization point.
• EEC: Spanner/TrueTime and Calvin-style deterministic systems spend latency budget (commit-wait ~2× clock uncertainty, ~5–10 ms) to keep consistency even in the common case.
• Classify systems both halves: Spanner = PC/EC (consistent under partition by stalling, consistent otherwise by waiting); Dynamo/Cassandra = PA/EL (available under partition, low-latency otherwise, consistency dialed per op); etcd/ZooKeeper = PC/EC for coordination-sized data only.

Draw it as the triangle-plus-else and place two systems on it — instant senior signal.

The Consistency Spectrum

Strongest to weakest, each with its guarantee and its price. Formal definitions and the Alice-and-Bob recency examples are the deep dive in Linearizability; here is the ordering interviewers expect you to rattle off:

Two nuances that score points. First, linearizability vs serializability: linearizability is a single-object recency guarantee; serializability is multi-object transaction isolation (the "I" in ACID). Spanner gives both (externally consistent transactions); a linearizable register store with no transactions gives only the first. Second, CRDTs (see CRDTs) let AP systems converge without last-write-wins data loss — counters, sets, and collaborative-text types merge commutatively.

CP vs AP: System Mapping

How to choose in an HLD interview — three sentences: coordination metadata (locks, leader election, config, unique IDs) goes to a CP store because split-brain there corrupts everything; user-facingOLTP with a partitionable keyspace goes leaderless/quorum-tunable so one AZ failure doesn't halt writes; and cross-region, the speed of light (~70–100 ms RTT US–Asia) forces the question "is linearizability across oceans worth 200 ms on every write?" — almost always no, hence single-region-linearizable plus async cross-region replication as the default global topology.

Trade-offs

Interview One-Liners

• Q: CAP — pick two? A: Only during a partition, and partitions are the rare case; the daily trade is PACELC's else-branch — latency vs consistency — tuned per operation, not per system.
• Q: When would you choose CP over AP? A: When split-brain corrupts invariants: locks, leader election, uniqueness constraints, ledger writes — and I'd isolate that CP state in etcd/ZooKeeper rather than making the whole product CP.
• Q: Linearizable vs serializable? A: Linearizability is single-object recency (reads never go stale); serializability is multi-object transaction isolation — you can have either without the other.
• Q: How does Cassandra tune CAP per query? A: R+W vs N quorums: QUORUM/ALL leans CP with cross-replica latency; ONE leans AP with possible staleness — same cluster, dial per operation.
• Q: Strong consistency across three continents? A: Physics says no without ~200 ms writes, so: linearizable within the home region, async replication + CRDT/LWW merge globally, and failover accepts bounded staleness.
• Q: What's the cheapest consistency that still feels correct in a feed? A: Causal + read-your-write session guarantees — replies after posts, own posts visible instantly — without paying quorum RTT on every read.
• Q: Where do vector/Lamport clocks fit? A: They track causality so replicas can order concurrent writes and detect conflicts — the machinery under causal stores and Dynamo-style reconciliation.

Related

• Linearizability — the formal deep dive (recency guarantee, use cases)
• Quorums — the R+W>N mechanism behind tunable consistency
• Single Leader Replication — the cheapest path to linearizable reads/writes
• Leaderless Replication — the AP archetype (hinted handoff, read repair)
• CRDTs — convergence without data loss on the AP side
• Coordination Services — where CP systems actually get used
• Raft Leader Election + Raft Writes — how quorum consistency is implemented
• Messaging and Event Queues — queues as AP buffering in front of CP state