Day 2: Consistency Models

Phase 1 · May 21, 2026

Agenda (2–3 hours)

• Read (45 min): Herlihy & Wing "Linearizability" §1–3; Vogels "Eventually Consistent" (ACM Queue 2009)
• Study (45 min): Each consistency model, its definition, and a counter-example for weaker models
• Practice (45 min): Draw execution diagrams showing which histories are allowed under each model
• Challenge (30 min): Classify the consistency model of Redis Cluster, CockroachDB, and Cassandra (with justification)

The Consistency Hierarchy

Stronger guarantees → fewer anomalies, higher latency/cost:

Linearizability (strongest)
    ↓
Sequential consistency
    ↓
Causal consistency
    ↓
Read-your-writes
    ↓
Monotonic reads
    ↓
Eventual consistency (weakest)

Every system lives somewhere on this spectrum.

Linearizability

The gold standard for single-object operations.

Definition: every operation appears to take effect atomically at some point between its invocation and response, and that point is consistent with real-time ordering.

Implications:

• A read sees the most recent completed write
• Once a value is observed, no older value is ever returned
• Equivalent to a single-threaded execution on one machine

Used by: etcd, ZooKeeper (with caveats), Spanner

Sequential Consistency

Weaker than linearizability — drops the real-time requirement.

Definition: all operations appear in some sequential order that is consistent with the program order of each individual process.

Process A:  W(x=1)          R(y) → 0
Process B:          W(y=1)  R(x) → 0

Both reads returning 0 is allowed under sequential consistency (but NOT linearizability).

Used by: some CPU memory models (TSO variants)

Causal and Eventual Consistency

Causal consistency:

• If A caused B (write → read dependency), all processes see A before B
• Concurrent operations may be seen in different orders
• Used by: COPS, Cassandra with lightweight transactions

Eventual consistency:

• If no new updates are made, all replicas will eventually converge
• No constraint on when or order of intermediate states
• Anomalies: stale reads, lost updates, write conflicts
• Used by: DynamoDB (eventually consistent reads), Cassandra default, DNS

Key Takeaways

• Linearizability = real-time atomic operations; hardest to achieve, easiest to reason about
• Sequential consistency = global order exists but ignores real time
• Causal consistency = cause-before-effect is preserved; concurrent writes may diverge
• Eventual consistency = only a liveness guarantee; anything can happen in between

Tomorrow: the CAP theorem — why you fundamentally cannot have strong consistency during network partitions without sacrificing availability.