CENTRAL UNIVERSITY
LectureCAP, PACELC and Consistency Models
A story about real trade-offs in distributed systems
/ CAP, PACELC and Consistency Models · Central University
A story about real trade-offs in distributed systems
A story about real trade-offs in distributed systems
From theorems to engineering decisions
First — CAP: C/A/P and correct reading.
Then — PACELC profile for product needs.
Finale — Jepsen, models and Cassandra.
During a partition you cannot guarantee both C and A simultaneously
For shared-data systems
C: linearizability
A: live node responds
P: message loss
Formal definitions over marketing
Consistency
One global order
Read-after-write sees the latest value.
CAP means linearizability
Availability + Partition
Availability: response without deadline
Partition: message loss
Together they conflict with C
Why this is stricter than 'just identical data'
Total order matches real time
Operation appears instant
System behaves as one node
Replica desync violates guarantee
Weak on timing, but strong on obligation
Live node must respond
No deadline, but termination
Waiting for sync loses A
CP often returns error/timeout
From conjecture to proof
1998: Brewer formulates CAP.
1999: harvest/yield, fault tolerance.
2000: CAP reaches PODC.
2002: Gilbert/Lynch prove it.
Useful, but too crude
CAP trade-off arises during partition.
Peacetime can deliver C and A.
Strategy is often per-operation.
Need degradation rules, not labels.
You can't ignore them
Packet loss and zone breaks happen
Question: system behavior during partition.
Timeouts create false partitions
Need enter/exit runbooks
One product can combine CP and AP behavior
Money often requires CP
Feeds often allow AP
APIs can behave differently
Stale reads must be explicit
Architecture is about gradations
Availability = uptime/error budget.
Consistency: eventual → linearizable.
Partition can be partial and asymmetric.
Manage probability and impact.
Detect → Decide → Recover
Detect / Decide
Symptoms: latency, majority, heartbeats
Policy: fail-fast or stale
Restrictions: read-only/degrade
Recover
Replica reconciliation
Conflict resolution and compensation
Track lag, conflicts, recovery
Partition often starts with timeouts
Slow networks look partitioned.
'Wait longer' helps C.
'Respond faster' helps A, risks C.
Timeout/retry policy is CAP policy.
Terminology confusion breaks design
C in ACID
Business and schema invariants
Balance and foreign keys
Transactional correctness
C in CAP
Distributed linearizability
Nodes see incompatible results
Replicas and network under failure
Soft state, eventual consistency
Temporary inconsistency buys A.
Soft state changes itself.
Eventual convergence without new writes.
A different guarantee profile.
Why the theorem is rigorous
C = atomic consistency.
A: healthy node responds.
P: arbitrary message loss.
Read/write object cannot give A+C.
Two-node contradiction proof
Assume A + atomic C exists
G1 and G2 lose all messages
Write to G1, read from G2
A needs response; C needs write
Clocks do not remove CAP
Clocks and deadlines help.
Under message loss, A/C conflict persists.
Timeouts detect, not remove CAP.
Architect still chooses incident behavior.
Describe critical operations.
Agree on denial/degradation limits.
Link timeouts/retries to CAP strategy.
Prepare reconciliation and compensation processes before an incident.
CAP is managed degradation, not a theoretical puzzle.
PACELC adds normal mode
P-block — With partition, choose availability or consistency.
ELSE-block — Healthy network: choose L or C.
Why it matters — Most decisions happen in normal mode.
if P then A/C else L/C
P: availability or consistency
ELSE: latency or consistency
Trade-off exists always
Explains modern databases better
CAP ignores normal mode
Partitions are rare; Cassandra is eventual.
Answer: latency and throughput.
Cross-region sync raises p99.
PACELC exposes peacetime choice.
The greatest architectural pain happens right here
Global order needs coordination
Coordination hurts p95/p99
Eventual/causal changes app logic.
Compare delay cost vs read error.
PA/EL, PC/EC, PA/EC, PC/EL
A profiles
PA/EL: A during P, L normally.
PA/EC: A during P, C normally.
C profiles
PC/EC: C during P and normally.
PC/EL: C during P, L normally.
Formalize profile in ADRs/SLOs.
A typical choice for high-scale content scenarios
During partition, responds despite temporary desync.
Normal mode optimizes latency/throughput.
Examples: Cassandra, DynamoDB, Riak.
Needs app-level compensation mechanisms.
When correctness beats latency
Partition blocks some operations.
Peacetime also favors consistency.
Examples: Spanner-like systems.
Domains: payments, ledger, limits.
A in incidents; C in normal mode
Partition: avoid service interruption.
Normal mode: stronger consistency.
Depends on quorum/read concern.
Staleness allowed only in outages.
Strict during failures, fast during normal network
Partition keeps strictness; some requests reject.
Normal mode optimizes latency.
Requires fine-grained routing/failover.
Niche: strict incidents, good UX.
Not 'which DB is trendy' but 'which error is unacceptable'
C priority
Payments and transactions.
Balances/limits without oversell.
Legal journals and audit.
L/A priority
Feeds and recommendations.
Search with acceptable drift.
Near-real-time analytics.
PACELC must map to team metrics
Set p95/p99 and stale-read share.
Separate downtime and freshness budgets.
Write-path: latency, lag, conflict rate.
Read-path: lagging-replica share and read-version age.
CAP: failure mode; PACELC: plus normal mode.
Key choice is often else: L vs C.
Category comes from business error cost and SLA.
Validate with tests and observability.
PACELC budgets engineering trade-offs.
From documentation to verifiable guarantees
What it is — Kyle Kingsbury's project for correctness testing under failures.
What it does — Generates operations, injects failures and checks history.
Why it matters — Separates guarantees from marketing.
Bugs appear under failures
Checks partition/crash/clock skew.
Found lost writes and atomicity bugs.
Vendors fix and clarify guarantees.
Surfaces risks before adoption.
Setup → Generate → Nemesis → Record → Check
Setup: cluster and expected model
Generate: concurrent read/write/CAS
Nemesis: failures and anomalies
Record + Check: find counterexamples.
Why 'almost correct' systems break
Network scenarios
Full partition between node groups.
Asymmetric loss / one-sided visibility.
High jitter, intermittent links.
Process / timing
Process or leader crash/restart.
Clock skew / time sync drift.
Overlapping failure scenarios.
Where promises and reality diverge most often
Lost writes during failover/split-brain.
Read-your-writes and stale reads.
Transaction guarantee anomalies under concurrent load.
'Strong consistency' without a model.
Serializable (RDBMS) and Linearizable (Distributed)
Transactional branch — Isolation and allowed anomalies.
Distributed branch — Global read/write order.
Apex — Strict Serializable unites both axes.
Similar words, different guarantees
Serializable
Equivalent to serial transaction order.
Order may ignore wall-clock time.
Focus: isolation anomalies.
Linearizable
One commit point per operation.
Order respects real completion time.
Focus: replicated read/write.
Guarantee should match error cost
Eventual fits acceptable staleness.
Causal fits user causal chains.
Linearizable fits read/write truth.
Strict Serializable protects invariants.
1) Formalize invariants and unacceptable errors.
2) Describe partition mode per operation.
3) Choose PACELC and latency/consistency budgets.
4) Fix the target consistency model.
5) Validate with chaos/Jepsen before critical load.
Experiments confirm architectural trade-offs.
Bigtable + Dynamo, tunable consistency, and AP profile
Origins — Bigtable: wide-column, LSM write path. Dynamo: hashing, gossip, peer-to-peer.
Classification — CAP: AP. PACELC: PA/EL.
Practice — Tunable consistency levels.
Guarantee depends on R/W levels
Writes: ANY, ONE, QUORUM, ALL.
Reads: ONE, QUORUM, ALL.
W+R>RF improves latest-read odds.
QUORUM balances correctness/latency.
LSM write path + token ring + repair
Write path and storage
Commit Log → MemTable → SSTable.
Compaction removes old versions.
LSM optimizes writes.
Distribution and resilience
Consistent hashing + vnodes.
Gossip detector, no master.
Repair drives convergence.
CAP: https://system-design.space/chapter/cap-theorem
PACELC: https://system-design.space/chapter/pacelc-theorem
Consistency Models (Jepsen): https://system-design.space/chapter/jepsen-consistency
Cassandra: https://system-design.space/chapter/cassandra
All 4 source chapters from system-design.space in one place.