Distributed Systems: Consistency Models¶

The CAP Theorem¶

In distributed systems, you can only have 2 of 3: - Consistency: All nodes see the same data - Availability: Every request gets a response - Partition Tolerance: System works despite network partitions

Consistency Models (Strongest to Weakest)¶

1. Linearizability (Strongest)¶

• Operations appear to execute atomically
• Real-time ordering respected
• Example: Single-server systems

2. Sequential Consistency¶

• Operations appear in some total order
• Each process's operations appear in program order
• Example: Most traditional databases

3. Causal Consistency¶

• Causally related operations ordered
• Concurrent operations may be seen in different orders
• Example: Version vectors, vector clocks

4. Eventual Consistency (Weakest)¶

• All replicas eventually converge
• No ordering guarantees
• Example: DNS, CDNs

Practical Considerations¶

Implementation Patterns¶

Quorum Systems¶

N = Total replicas
W = Write quorum
R = Read quorum

Strong consistency: W + R > N
Example: N=3, W=2, R=2

Vector Clocks¶

Track causality across nodes:

Node A: {A:1, B:0}
Node B: {A:0, B:1}
After sync: {A:1, B:1}

Real-World Examples¶

• Spanner: Linearizable (TrueTime)
• DynamoDB: Eventually consistent (default)
• CockroachDB: Serializable
• Cassandra: Tunable consistency