PACELC Theorem

PACELC works because replication forces a standing decision on every write: the coordinator either blocks until enough remote replicas acknowledge — paying latency so that a later read is guaranteed to see the value — or returns the instant one local copy is durable, winning latency but leaving a staleness window until asynchronous propagation catches up. That knob exists whether or not the network is currently partitioned, which is exactly the case CAP is silent about.

The CAP recap, stated correctly

CAP says that during a network partition (P) a replicated system must give up either consistency (C) or availability (A). Traditional ACID relational stores (MySQL, PostgreSQL, Oracle) lean CP: a node that cannot confirm it holds the latest committed state refuses to answer. The genuinely AP, quorum-based, eventually-consistent stores are the Dynamo lineage — Cassandra, Amazon DynamoDB, Riak — which answer from whatever local copy they have and reconcile later.

One clarification the source material usually botches: Redis is not an AP eventually-consistent store. Standalone and Cluster Redis are single-primary with asynchronous replication to replicas. It is not a quorum store that returns divergent-but-mergeable values; instead a failover can silently drop writes the old primary had already acknowledged. Grouping Redis under "BASE/AP, answers without checking peers" conflates two very different models — a single-primary latency-first store versus a multi-master eventually-consistent one. Keep them separate.

CAP's blind spot: what governs the trade-off when there is no partition? A partition is rare; the system spends 99.9% of its life in the non-partitioned state, and it is still making a consistency choice there. That is the gap PACELC fills.

The theorem

For a system that replicates data:

• if Partition (P) — trade Availability (A) against Consistency (C) (this is just CAP);
• Else (E), when running normally — trade Latency (L) against Consistency (C).

The classification tag reads P?/E? — e.g. PA/EL means "favour availability under partition, favour latency otherwise." The crucial nuance: the tag describes a configuration, not a database. Most modern stores expose the L-vs-C knob per operation (Cassandra's consistency level, DynamoDB's strong-vs-eventual read flag, MongoDB's write/read concern), so the same product can be EL for one query and EC for the next.

Worked trace: the Else-branch knob in Cassandra

Setup: a keyspace with replication factor RF = 3, one replica per availability zone. The coordinator happens to be replica A (local, ~0.8 ms to persist); replicas B and C are cross-AZ, ~6 ms RTT away. The row user:42 currently holds balance = 90 on all three. A client issues balance = 100. No partition exists — we are purely in the E branch, choosing L vs C.

Path 1 — CL = ONE (the EL choice)

1. t = 0.0 ms — client1 writes balance = 100 at CL=ONE. Coordinator A persists locally and, because only one ack is required, immediately dispatches async copies to B and C.
2. t = 0.8 ms — A returns success to client1. Total write latency ≈ 0.8 ms. B and C have not applied the mutation yet.
3. t = 1.0 ms — client2 reads user:42 at CL=ONE; the coordinator routes it to the nearest replica, C.
4. C still holds the old value → returns balance = 90. The read was fast (~0.5 ms) but stale.
5. t ≈ 6 ms — B and C finally apply the write; the cluster converges. Latency won; consistency was sacrificed for a ~5 ms window. That is EL.

Path 2 — CL = QUORUM read and write (the EC choice)

Now write and read both at QUORUM (2 of 3). The write blocks until A and the faster of B/C ack → ≈ 6 ms. A QUORUM read contacts 2 replicas and returns the value with the highest timestamp. Because W + R = 2 + 2 = 4 > RF = 3, the read set and write set are guaranteed to overlap in at least one replica that saw the completed write → client2 reads 100. Consistency won, at the cost of ~5 ms extra latency and no answer if two replicas are down.

Classifying real systems

• Cassandra, DynamoDB, Riak — PA/EL. Under partition they stay writable on both sides and reconcile later (A over C); with no partition their default low consistency levels favour latency (L over C). Both branches lean the same way, which is why the Dynamo lineage is the canonical PA/EL family. Note: crank both to QUORUM and Cassandra becomes EC, as traced above — the label follows the config.
• Bigtable, HBase — PC/EC. Each key range (region/tablet) is owned by exactly one server backed by a strongly-consistent log (HDFS/Colossus). If that server is unreachable, the range is simply unavailable until reassigned — consistency over availability under partition, and there is no weaker-consistency fast path in the normal case either. Consistent in both branches.
• Spanner — PC/EC, but by a different mechanism. It refuses to sacrifice consistency and refuses eventual consistency; instead it pays latency — TrueTime commit-wait stalls each commit by roughly twice the clock-uncertainty bound (single-digit ms) to guarantee global linearizability. It is the instructive contrast to Cassandra-QUORUM: same EC outcome, latency spent deliberately rather than tuned away.
• MongoDB — PA/EC or PC/EC by configuration. Primary/secondaries with asynchronous replication. With w:1 (the classic default) an acknowledged write lives only on the primary; if that primary is partitioned onto the minority side and steps down, its un-replicated writes roll back — so under partition it favoured availability and lost durability of those writes → PA; with no partition, reads from the primary see the latest → EC. Switch to w:majority (the default since MongoDB 5.0) plus majority/linearizable reads and a write is not acknowledged until a majority holds it, so a minority-side primary cannot ack — it gives up availability to preserve consistency → PC/EC.

Pitfalls

• Treating PACELC as a fixed per-database label. "Cassandra is AP" is half-true and operationally misleading. Consistency is chosen per query via CL / read-concern / consistency flags. Two services on the same cluster can sit on opposite sides of the E-branch.
• Assuming W + R > N gives you linearizability. Quorum overlap only guarantees a read observes the latest completed write. Concurrent writes still race: Cassandra resolves conflicts by last-write-wins on timestamps, so two overlapping updates can silently drop one (a lost update). For real invariants you need lightweight transactions / compare-and-set, not just quorum math.
• Under-pricing the EC latency tail. "Else-consistency" is not free — a quorum write waits for the slowest replica in the quorum, so cross-region deployments push p99 latency to the WAN RTT. The mean looks fine; the tail is where consistency is billed.
• Obsessing over the P branch. Partitions are rare; the E branch governs almost every request. Teams argue for hours about partition behaviour while shipping a default consistency level that quietly serves stale reads all day.
• Clock skew breaking LWW. PA/EL stores that reconcile by wall-clock timestamps assume synced clocks. A drifting node can stamp a stale write as "newer" and overwrite good data — the failure is silent.

When to use PA/EL — and when NOT to

Reach for PA/EL (Cassandra, DynamoDB eventual reads, Riak) when the workload is write-heavy and geo-distributed, "always writable" is a hard requirement, and a few milliseconds-to-seconds of staleness is harmless: activity feeds, view/like counters, telemetry and IoT ingest, shopping carts, session stores. Gain: low tail latency and writes that survive an AZ or region loss. Cost: the application must tolerate or merge stale and concurrent values — you inherit last-write-wins lost updates unless you model data as CRDTs / commutative operations or merge in the app.

Prefer PC/EC (HBase, Bigtable, Spanner, MongoDB w:majority) when a stale or lost write is a correctness bug: financial ledgers, inventory decrement, uniqueness constraints, anything needing read-your-writes or cross-row transactions. Gain: reads reflect the latest committed state; far simpler application logic. Cost: higher and more variable latency (Spanner's commit-wait, single-primary bottlenecks), and reduced availability during partition — the minority side rejects requests.

Choosing against named alternatives

• Cassandra-QUORUM vs Spanner (both land at EC). Cassandra tunes toward EC per query and is cheap and operable, but has no multi-partition transactions and resolves conflicts by LWW. Spanner gives global, transactional linearizability out of the box — at the price of commit-wait latency, cost, and Google/CockroachDB-class infrastructure. Choose Cassandra-QUORUM when you need single-key freshness cheaply; choose Spanner when you need cross-partition ACID transactions and will pay the latency.
• Cassandra PA/EL vs MongoDB PA/EC. Both stay available under partition, but MongoDB funnels reads through one primary (fresh in the normal case, EC), whereas Cassandra can serve any replica (fast but stale, EL). Choose MongoDB for read-your-writes with modest scale; choose Cassandra for multi-region write availability and linear write scaling.

Crisp rule: choose PA/EL when availability and latency outrank freshness and your writes commute; prefer PC/EC when a stale or lost write would be a bug.

Takeaways

• PACELC adds the question CAP ignores: with no partition, replication still forces a latency-vs-consistency trade on every request — the branch that governs almost all of runtime.
• The mechanism is the acknowledgment rule: block for a quorum (consistent, slow) or return on one local copy (fast, stale). W + R > N guarantees the read set overlaps the last completed write.
• The label is a configuration, not a database: Cassandra is EL at CL=ONE and EC at QUORUM; MongoDB is PA/EC at w:1 and PC/EC at w:majority.
• EC is not free — you pay it in the p99 tail (slowest replica in the quorum); AP/LWW is not free either — you pay it in silent lost updates and clock-skew hazards.

Sources: Daniel Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design" (IEEE Computer, 2012) — the paper that coined PACELC; Eric Brewer's CAP conjecture and the Gilbert–Lynch proof; Martin Kleppmann, Designing Data-Intensive Applications (quorums, replication, linearizability); the Cassandra consistency-level docs, Amazon DynamoDB developer guide, MongoDB write-concern/read-concern docs (default w:majority since 5.0), and the Google Spanner / TrueTime paper (OSDI 2012). Re-authored and deepened for this guide — Redis mislabeling corrected, quorum example traced with real values.