System Design: Consistency, Availability & CAP Theorem

Master distributed systems trade-offs including CAP and PACELC theorems, consistency models, quorum formulations, vector clocks, and conflict resolution.

1. CAP Theorem Explained

Formulated by Eric Brewer, the CAP Theorem states that a distributed data system can simultaneously provide at most two out of three guarantees: Consistency (C), Availability (A), and Partition Tolerance (P).

Because physical networks inevitably experience dropped packets or split networks (Partition Tolerance is mandatory in distributed systems), systems must choose between Consistency (CP) or Availability (AP) during a network partition.

CAP Theorem & PACELC Distributed Systems Trade-Off Matrix

System Design

Analyzing CP vs AP trade-offs during network partitions alongside PACELC normal operation behavior

100%
Loading system design canvas…

Consistency (C - Linearizability)

Every read request receives the most recent write or an error. All nodes in the cluster observe the exact same state simultaneously.

Availability (A)

Every non-failing node returns a non-error response to every request, though the data returned is not guaranteed to be the most recent.

Partition Tolerance (P)

The system continues operating despite network packet loss or communications failures dividing nodes into isolated sub-networks.

2. PACELC Theorem

The PACELC theorem extends CAP by describing system trade-offs not only during network partitions, but also during normal error-free operations.

PACELC Breakdown Formula

  • If Partition (P):Choose between Availability (A) and Consistency (C).
  • Else Normal (E):Choose between Latency (L) and Consistency (C).

PC/EC Systems (e.g. HBase, MongoDB)

Prefers consistency both during network partitions and during normal operations. Sacrifices availability during partitions and incurs higher read/write latency during normal operation to coordinate locks.

PA/EL Systems (e.g. Apache Cassandra, DynamoDB)

Prefers availability during partitions and low latency during normal operation. Uses asynchronous replication, accepting eventual consistency.

3. Strong Consistency vs Eventual Consistency

Consistency spectrums range from strict linearizability to probabilistic convergence over time.

Strong Consistency

After a write completes, all subsequent reads across any cluster node immediately return the updated value. Requires synchronous coordination and higher latency.

Eventual Consistency

If no new updates are made, all replicas across the cluster will eventually converge and return identical values. Delivers high availability and sub-millisecond latency.

4. Specialized Consistency Models

Causal Consistency

Operations that are causally related must be observed in the same order by every node across the system. Unrelated operations can be observed in different order.

Read-Your-Writes Consistency

Guarantees that a user will always observe their own updates on subsequent reads, even if other users briefly observe stale data.

Monotonic Reads

Guarantees that once a client observes a particular data version, they will never observe an older version on subsequent reads.

5. Quorum-Based Consistency

Quorum systems configure how many database replica nodes must participate in read and write operations to tune consistency guarantees dynamically.

Quorum-Based Read and Write Consistency Architecture

System Design

Visualizing replica overlap guarantees when Read Quorum (R) + Write Quorum (W) > Total Replicas (N)

100%
Loading system design canvas…

Strong Quorum Formula: R + W > N

When the number of read replicas (R) plus the number of write replicas (W) is strictly greater than total replicas (N), at least one replica in the read set is guaranteed to contain the latest write.

  • Example:N = 3, W = 2, R = 2 -> (2 + 2 = 4 > 3). Strong consistency guaranteed.

Eventual Quorum Formula: R + W <= N

When read and write quorums do not overlap sufficiently, reads may return stale data versions until background read repair or anti-entropy sync completes.

Review how the Quorum Cluster Evaluator below calculates quorum overlap and triggers automated read repairs.

Quorum Evaluator & Background Read Repair Implementation

Calculating R + W > N mathematical consistency guarantees and repairing stale nodes

6. Conflict Resolution Strategies

In eventual consistency or multi-master systems, concurrent write operations on different nodes create data conflicts that must be resolved.

Last Write Wins (LWW)

Assigns wall-clock timestamps to write operations and retains the write with the latest timestamp. Simple to compute, but vulnerable to wall-clock drift inaccuracies.

Vector Clocks

Tracks logical causality timestamps across nodes as a array of (nodeId, counter) tuples. Accurately detects concurrent write conflicts for application-level resolution.

Conflict-Free Replicated Data Types (CRDTs)

Specialized data structures (such as PN-Counters or Observed-Remove Sets) designed so concurrent operations merge deterministically without locks or coordination.

Examine how the Vector Clock engine below tracks event causality and flags concurrent modification conflicts.

Vector Clock Causality & Conflict Detection Algorithm

Tracking event logical clocks across nodes to detect concurrent branching conflicts

CAP Theorem & Consistency Knowledge Verification

1. What does Partition Tolerance (P) guarantee in the CAP theorem?

2. What tradeoff does the PACELC theorem highlight during normal operation?

3. What condition guarantees strong consistency in Quorum-based systems?

4. How does Read-Your-Writes consistency benefit users?

5. What characterizes Conflict-Free Replicated Data Types (CRDTs)?