Part II — Distributed Data
Consistency & Consensus
The strongest guarantees distributed systems can offer — and the algorithms (quorums, consensus protocols) that make them possible despite unreliable networks.
Given everything unreliable about networks, clocks, and process pauses, how does a distributed system ever offer a strong guarantee about the data it holds? Two ideas do almost all of the work: quorums for read/write consistency, and consensus algorithms for getting a cluster to agree on one value even when nodes fail.
Quorums
In a leaderless (Dynamo-style) system with N replicas, a client can require a write to succeed on W replicas and a read to succeed on R replicas before considering the operation complete. The guarantee comes from simple arithmetic:
W = 2, R = 2, N = 3 (W + R > N) — the write set and read set are guaranteed to overlap, so at least one replica you read from has the latest write.
Quorums let you tune the read/write latency tradeoff explicitly: a common configuration is N=3, W=2, R=2 — tolerates one replica being down for either reads or writes, while still guaranteeing overlap.
Linearizability
The strongest single-object consistency guarantee: once a write completes, every subsequent read (from any client, on any replica) must return that value or a later one — the system behaves as if there’s only a single, up-to-date copy of the data, even though it might be replicated across many machines. It’s expensive (in the presence of network partitions, you cannot have it and stay fully available — this is the real content behind the informally stated “CAP theorem”), but it’s what you actually want for things like a lock service or a uniqueness constraint (usernames, account IDs).
Consensus
Getting a cluster of nodes to agree on one value — who the leader is, whether a transaction committed, what the next entry in a replicated log is — despite node failures and message loss, is the consensus problem. It’s provably impossible to solve deterministically in a fully asynchronous network with even one faulty node (the FLP impossibility result) — which is why real algorithms make practical assumptions (like using timeouts to detect failure) rather than trying to solve the pure theoretical problem.
Raft and Paxos are the two consensus algorithms used in essentially every production system that needs this guarantee. Both work by having nodes vote: a value (or a leader) is only considered decided once a majority of nodes have agreed — which is exactly why consensus clusters are deployed with an odd number of nodes (3 or 5), so a majority is always well-defined even after some nodes fail.
# Simplified Raft leader election
1. A node's election timeout fires (no heartbeat from a leader recently).
2. It becomes a candidate, increments its term, votes for itself,
and requests votes from all other nodes.
3. If it receives votes from a majority of nodes, it becomes leader
for that term and starts sending heartbeats.
4. Any node that sees a higher term steps down immediately.