Consistency & Consensus

A single database on a single machine is simple. Every read sees the latest write. There's one copy of the data, one source of truth. But a single machine can fail, can't handle millions of requests, and is in one geographic location. So we distribute — we replicate data across multiple machines in multiple locations. And that's where everything gets hard.

The core tension: we replicate data for reliability and performance, but replication introduces the possibility of conflicting updates, stale reads, and disagreement between nodes. Consistency and consensus are the tools we use to manage this tension.

Why We Replicate Data

Problems Introduced by Replication

The CAP theorem states that a distributed system can provide at most two of three guarantees simultaneously: Consistency, Availability, and Partition Tolerance. Since network partitions are inevitable in any distributed system, the real choice is between Consistency and Availability during a partition.

Why Partition Tolerance Is Non-Negotiable

In any real distributed system, network partitions will happen. Cables get cut. Routers fail. Cloud availability zones lose connectivity. You can't choose "no partitions" — you can only choose how to behave when they occur. This means the real choice is always CP or AP.

Network partition splits the cluster:

  [Node A, Node B]  ←— can't talk to —→  [Node C]

Client writes "balance = $500" to Node A.
Node A and B are updated. Node C still has the old value ($1000).

CP System (e.g., HBase):
  → Node C stops accepting reads/writes
  → Returns error: "Service unavailable"
  → When partition heals, Node C syncs and becomes available
  → Guarantee: no client ever sees stale data

AP System (e.g., Cassandra):
  → Node C keeps accepting reads/writes
  → Returns old value: "balance = $1000" (stale!)
  → When partition heals, conflict resolution merges the data
  → Guarantee: every client always gets a response

CAP only describes behavior during partitions. But what about normal operation — when there's no partition? That's where PACELC comes in. It extends CAP to cover the full picture.

If there is a Partition (P):
  → Choose between Availability (A) and Consistency (C)

Else (E) — normal operation, no partition:
  → Choose between Latency (L) and Consistency (C)

Full notation: PA/EL, PC/EC, PA/EC, PC/EL

Examples:
  Cassandra  → PA/EL  (Available during partition, low latency normally)
  DynamoDB   → PA/EL  (Same — availability and speed first)
  HBase      → PC/EC  (Consistent during partition, consistent normally)
  MongoDB    → PC/EC  (Strong consistency by default)
  Cosmos DB  → Configurable (you choose per query!)

Why PACELC Is More Realistic Than CAP

CAP only matters during partitions — which are rare (minutes per year). PACELC captures the trade-off you face every single request: do you wait for all replicas to confirm (consistency, higher latency) or respond from the nearest replica immediately (low latency, possibly stale)?

This is the most practical trade-off you'll face in system design. Strong consistency means every read returns the latest write. Eventual consistency means reads might return stale data, but all replicas will converge over time.

Scenario: User updates their profile name from "Alice" to "Alicia"

Strong Consistency:
  1. Write "Alicia" → wait for all replicas to confirm
  2. Any subsequent read from ANY server → "Alicia"
  3. User refreshes page → sees "Alicia" immediately
  4. Latency: 50-200ms (coordination across replicas)

Eventual Consistency:
  1. Write "Alicia" → acknowledged after 1 replica confirms
  2. Read from same server → "Alicia" ✅
  3. Read from different server → might still show "Alice" ⏳
  4. After 100ms-2s, all replicas converge → "Alicia" everywhere
  5. Latency: 5-20ms (no coordination)

User experience impact:
  → User updates name, refreshes, sees old name briefly
  → "Did my update not save?" → confusion
  → Fix: read-your-own-writes consistency (read from the replica you wrote to)

When Is Eventual Consistency Acceptable?

Linearizability is the strongest form of consistency. It guarantees that all operations appear to execute in a single, global order — as if there's only one copy of the data, even though it's replicated across multiple nodes.

Linearizability vs Eventual Consistency

Timeline:
  T1: Client A writes x = 1
  T2: Client A gets acknowledgment (write complete)
  T3: Client B reads x

Linearizable:
  Client B reads x → MUST return 1
  Because the write completed (T2) before the read started (T3),
  the read must see the write's effect. No exceptions.

Eventually Consistent:
  Client B reads x → might return 0 (old value)
  The write happened, but the replica Client B is reading from
  hasn't received the update yet. It will... eventually.

Linearizability = real-time ordering guarantee
Eventual consistency = no ordering guarantee (just convergence)

Let's design the consistency model for two real systems — a banking platform and a social media platform — and see how the same concepts lead to completely different decisions.

Consistency vs Availability

Latency vs Correctness

Complexity vs Guarantees

Conceptual, scenario-based, and trick questions you're likely to encounter.

These misconceptions trip up engineers in interviews and lead to bad architectural decisions.