CAP and Consistency Models

Brewer's conjecture (2000), proved by Gilbert & Lynch (2002): a distributed system cannot simultaneously provide all three of:

• Consistency — every read sees the most recent write (this is actually linearizability, not just any consistency model).
• Availability — every request to a non-failing node returns a non-error response.
• Partition tolerance — the system continues to operate when the network partitions.

The critical misreading: partition tolerance is not optional. Real networks partition. The actual choice is: when a partition happens, do you sacrifice C (stay available with possibly stale data) or sacrifice A (refuse requests to preserve linearizability)? This is a binary choice during a partition, not a dial to turn. Calling a system "CA" just means you haven't thought through what happens when the network fails.

CAP only talks about behavior during a partition. Abadi's PACELC (2012) adds the normal-operation trade-off:

If there's a Partition, choose between Availability and Consistency; Else (no partition), choose between Latency and Consistency.

Examples:

• Cassandra — PA/EL: available during partition, low latency with tunable consistency at rest.
• DynamoDB (default) — PA/EL: eventual consistency for low latency.
• HBase / Zookeeper — PC/EC: consistent during partition, accepts higher latency.
• Spanner — PC/EC: linearizable always, pays with cross-datacenter commit latency (~10–100 ms).

PACELC makes explicit that consistency costs latency even when everything is healthy — which is the trade-off most engineers actually care about day-to-day.

Consistency is not binary. From strongest to weakest:

Linearizability is what most people mean when they say "strongly consistent." It's the model that makes a distributed register behave like a single-machine register to outside observers.

An execution is linearizable if you can find a linear order of all operations such that:

1. Each operation appears to take effect instantaneously at some point between its invocation and its response.
2. That linear order is consistent with real time (if op A completes before op B starts, A comes first).

In practice, achieving linearizability requires consensus or single-leader coordination — which is why it's expensive. Etcd and Zookeeper are linearizable (with quorum reads). Cassandra's QUORUM reads are not linearizable by default — you need SERIAL consistency for that, which engages Paxos per-operation.

A common gotcha: read-your-writes is weaker than linearizability. You can implement it with session tokens and sticky routing, with no inter-node coordination. Conflating the two leads to systems that feel consistent but silently violate ordering guarantees other clients can observe.

Causal consistency is the sweet spot for many applications: it respects the happens-before order (from the previous lesson's vector clocks) while allowing concurrent operations to be seen in different orders by different nodes.

The four classic session guarantees (Terry et al., 1994):

• Read-your-writes (RYW): after you write X, you always read X or something newer.
• Monotonic reads: if you read value V at time T, you never read something older at T' > T.
• Writes-follow-reads: if you read X then write Y based on it, Y is guaranteed to be visible after X everywhere.
• Monotonic writes: your writes are applied in the order you issued them.

Many "eventually consistent" systems offer some subset of these. MongoDB with read preference primary gives RYW; with secondaryPreferred it breaks it. Know your defaults.

Eventual consistency guarantees that if no new writes occur, all replicas will eventually converge to the same value. It says nothing about:

• When convergence happens.
• What value is chosen (you need a conflict resolution policy: last-write-wins, CRDT merge, application-level).
• What intermediate values clients may observe.

# Last-write-wins (LWW) — a common EC conflict policy
def resolve(replica_a, replica_b):
    # Dangerous: relies on clock synchronization
    return replica_a if replica_a.timestamp > replica_b.timestamp else replica_b

# Safer: Lamport timestamp or application-defined merge
def resolve_crdt(set_a, set_b):
    return set_a | set_b  # CRDT OR-Set: union is the merge

LWW with physical clocks silently loses writes when clocks skew. CRDTs (Conflict-free Replicated Data Types) give you eventual consistency with deterministic, lossless merges — but only for data structures that fit the CRDT algebra.

How to pick a consistency model:

• Financial transactions, inventory, leader election: linearizability. Use Spanner, CockroachDB, or a Raft-based store. Accept the latency.
• Social feeds, caches, analytics: eventual consistency. Use Cassandra, DynamoDB, or Redis with asynchronous replication. Design around stale reads.
• Collaborative editing, counters, shopping carts: causal consistency + CRDTs. Riak, Automerge, Yjs.
• User sessions (logged-in state): read-your-writes at minimum. Sticky sessions or a session store with synchronous replication to one replica.

The worst outcome is choosing eventual consistency for correctness-critical data because it's "faster," then papering over anomalies with application-level hacks that break under load. Measure the latency cost of stronger consistency first — it's often under 5 ms for intra-datacenter quorums.