Before we start, one number you will need in the harder problems. When we replicate a value across N machines, we often demand that a quorum — a majority — agree. Two quorums are used:
See the Replication and Quorums note for more; the picture below shows the overlap.
Answer: Consistency (C). The read returned the most recent successful write. That is the exact definition of CAP consistency (linearizability). Availability only promises a non-error answer, not necessarily the latest — so "latest write returned" specifically points to C.
Recall Solution 1.2
(a) etcd → CP
(b) Cassandra → AP
(c) DynamoDB → AP
(d) HBase → CP
Memory hook: coordination/config stores (etcd, ZooKeeper, HBase) refuse rather than lie → CP. Big shopping-scale key-value stores (Cassandra, Dynamo, Riak) stay up and reconcile → AP.
Recall Solution 1.3
False. CAP-C = linearizability (all replicas agree on one up-to-date value). ACID-C = preserving database invariants inside a single transaction (e.g. a constraint like balance ≥ 0). Different guarantees, same letter. See ACID vs BASE.
AP prioritises Availability, so N2must answer without erroring. But N2 never heard about x=5 (the partition blocked the message). So it returns the old value it holds (say the prior value). It sacrifices Consistency — the read is stale. Later, when the link heals, the systems reconcile (see Eventual Consistency).
Recall Solution 2.2
CP prioritises Consistency, so N2 must never return a wrong (stale) value. Since it cannot confirm it has the latest data (partition blocks confirmation), it refuses / returns an error / blocks until the partition heals or a majority is reachable. It sacrifices Availability.
Recall Solution 2.3
AP. A briefly-stale or mergeable cart is annoying but harmless; an unavailable "Add to Cart" button loses sales instantly, so availability wins and conflicts are resolved by merging (union of items).
CAP is not violated. CAP only speaks about partition time. Here there is no partition, yet we still saw staleness — because the leader chose low Latency (ack early) over Consistency (wait for followers). This is exactly what PACELC adds: if Partition → A vs C; Else → Latency vs Consistency. The stale read is the "Else, chose L" branch. See PACELC theorem.
Recall Solution 3.2
(a) Partition present, chose C, dropped A → A-vs-C, picked C (CP).
(b) No partition, chose speed → L-vs-C, picked L.
(c) Partition present, chose to answer → A-vs-C, picked A (AP).
Recall Solution 3.3
Not fully. A CP system guarantees consistency when it answers. During a partition it protects consistency by refusing (not by magically knowing the latest value). So it never returns stale data, true — but it achieves this partly by returning no data (errors). The correct statement: "a CP system never returns wrong data, but it may return no data." Consistency is bought with availability.
Minimum R: we need W+R>N⇒3+R>5⇒R>2⇒Rmin=3.Write fault tolerance: a write needs W=3 acks out of 5, so up to N−W=5−3=2 nodes may be down and writes still complete.
Geometrically (figure s01): a write set of size 3 and a read set of size 3 in a 5-node universe must overlap in at least W+R−N=3+3−5=1 node — that shared node carries the newest value.
Recall Solution 4.2
Surviving 3 failures needs N−W≥3⇒5−W≥3⇒W≤2, so Wmax=2.
Then R>N−W=5−2=3⇒Rmin=4. With W=2,R=4: W+R=6>5 ✓, so strong consistency is still achievable — but reads are now expensive (must reach 4 of 5). You traded cheap writes for pricey reads. This is the Replication and Quorums balancing act.
Recall Solution 4.3
Healthy network ⇒ Else branch of PACELC (L vs C).
Eventually consistent read: read a small subset (low R), possibly stale → picks Latency (and lower cost).
Strongly consistent read: read enough replicas to satisfy overlap / read the leader → picks Consistency at higher latency/cost.
So DynamoDB exposes the PACELC Else dial directly to the developer. See NoSQL Databases.
Overlap size =W+R−N=3+3−6=0. Since W+R=6=N, the inequality W+R>Nfails (6>6 is false). A write set {n1,n2,n3} and a read set {n4,n5,n6} can be disjoint — the read may miss the write entirely. No strong consistency guarantee. Fix: bump either W or R to make the sum ≥7. Even numbers of N are where people quietly lose consistency by choosing exact halves.
Recall Solution 5.2
(a) W=5,R=1:W+R=6>5 ✓ strong consistency. But writes need all 5 → zero write fault tolerance (N−W=0). Reads cheap. This is "write-all, read-one" — great reads, fragile writes.
(b) W=1,R=5:6>5 ✓ strong consistency. Writes cheap and tolerate 4 failures; reads need all 5 → zero read fault tolerance. Mirror image of (a).
(c) W=1,R=1:W+R=2>5 ✗ no consistency guarantee — pure "fast and loose," maximum availability both ways, eventual consistency only. This is the classic AP corner.
Figure s02 plots these on the W–R grid: everything strictly above the anti-diagonal W+R=N is strongly consistent.
Recall Solution 5.3
It is only honest if the system is not distributed across a network that can partition — e.g. a single node, or replicas on one machine that never lose contact. Then "no partitions ever occur," and with P removed you can hold C and A together.
Red flag: any real multi-machine system will experience partitions (cable cuts, GC pauses, dropped packets don't ask permission). So a "CA distributed database" marketing claim really means "we haven't decided what we do during a partition" — and it will silently become CP or AP under stress. P is not optional; see Distributed Systems and Consensus — Paxos & Raft for how real systems keep C by tolerating P.
Recall Solution 5.4
Survive 2 write failures: W≤N−2=3. Survive 2 read failures: R≤3. Strong consistency: W+R>5, i.e. W+R≥6. Best possible under both caps is W=3,R=3, giving W+R=6≥6 ✓. So W=3,R=3 works: overlap =6−5=1, and N−W=N−R=2 failures tolerated each. This is the sweet spot for N=5 — the reason "3 out of 5" majority quorums are so common.
