Chapter 9 is the climax of Part II. Given all the ways distributed systems fail (Chapter 8), how can we still build systems that behave correctly? The answer is consensus: getting multiple nodes to agree on something. But consensus does not exist in isolation — it is deeply linked to linearizability (the strongest consistency model), causality (the ordering of events), and total order broadcast (delivering messages in a agreed-upon sequence).
This chapter connects the dots between replication (Chapter 5), transactions (Chapter 7), and the failure models of Chapter 8, culminating in the algorithms that power ZooKeeper, etcd, and Raft — the backbone of modern distributed coordination.
Mission tie-in: every FAANG system design interview touches the material in this chapter. When asked "what happens if the leader fails?" the strongest answer includes fencing tokens, epoch numbers, and quorum-based leader election. When asked "is this system consistent?" the strongest answer distinguishes linearizability from causal consistency from eventual consistency, and explains the trade-off with availability and performance.
Replicated databases give different consistency guarantees. Most provide at least eventual consistency (convergence): if you stop writing and wait, all replicas will eventually return the same value. But this is a weak guarantee — it says nothing about when, and reads may return anything until convergence.
The problem is that eventual consistency is nothing like a variable in a single-threaded program. If you assign a value and read it back, you expect to see the value you just wrote — but in an eventually consistent database, you might not. Bugs due to weak consistency are subtle and hard to test for, because they manifest only under faults or high concurrency.
This chapter moves along the consistency spectrum from weak to strong:
Linearizability (also called atomic consistency, strong consistency, or external consistency) is a recency guarantee: it makes a replicated system appear as if there were only one copy of the data.
The canonical example: Alice and Bob are watching a football match. Alice refreshes her phone and sees the final score. She tells Bob. Bob refreshes his phone, but his request hits a lagging replica, and he sees the game still ongoing. This violates linearizability — because Bob's read happens strictly after Alice's, it must return the same or newer data.
Core definition: A system is linearizable if for every operation (read/write), there exists a point in time between the operation's invocation and its response (the "linearization point") such that the sequence of all operations, ordered by these points, forms a valid sequential history. Once a read returns a value, all subsequent reads (in real time) must return that same value or a newer one.
These two concepts are easily confused, but they are quite different:
| Serializability | Linearizability | |
|---|---|---|
| Scope | Transactions (multi-object operations) | Single-object reads and writes |
| Purpose | Isolation guarantee — transactions behave as if serial | Recency guarantee — single-copy illusion |
| Timing | Order may differ from real-time order; concurrent transactions can be serialized arbitrarily | Order must respect real-time: if operation A finishes before B begins, A must be before B in the linearization |
| Combined | Strict serializability = serializable + linearizable (e.g., 2PL-based implementations) | |
SSI (serializable snapshot isolation) is not linearizable: its whole point is to use snapshots that exclude recent writes, which breaks the recency guarantee.
Linearizability is required in several critical scenarios:
Single-leader replication requires that only one node is leader. If two nodes both believe they are leader, you get split brain. Leader election via a lock requires linearizability — all nodes must agree on who holds the lock. ZooKeeper and etcd provide this via consensus.
Usernames, email addresses, file paths — if you need to enforce uniqueness at write time and reject the second writer, you need linearizability. This is equivalent to an atomic compare-and-set.
When two communication channels exist (e.g., a file storage service and a message queue, or a database and a voice channel), non-linearizable systems can cause race conditions. Example: a web server writes a photo to storage, then sends a resize instruction via message queue. If storage is not linearizable, the resizer may read a stale version of the photo.
Different replication approaches provide different linearizability guarantees:
| Approach | Linearizable? | Why |
|---|---|---|
| Single-leader replication | Potentially | If reads are from leader or synchronously updated followers. But leader may be outdated if stale. |
| Consensus algorithms (Zab, Raft, Paxos) | Yes | Prevent split brain, stale replicas via epoch numbering and quorum voting. |
| Multi-leader replication | No | Concurrent writes on multiple nodes can conflict; async replication means no single up-to-date copy. |
| Leaderless (Dynamo-style) | Probably not | Strict quorums can still produce nonlinearizable behavior (see Figure 9-6). LWW with clock timestamps is definitely not. Synchronous read repair helps but cannot support compare-and-set. |
Key insight: even with strict quorums (w + r > n), leaderless systems can have nonlinearizable executions. If client A reads from one quorum and gets the new value, and client B reads from a different quorum and gets the old value (even though B's read starts after A's completes), linearizability is violated.
Linearizability forces a choice during a network partition: if a follower datacenter cannot reach the leader, it cannot service linearizable reads or any writes — it must return errors. Multi-leader systems can remain available during partitions but sacrifice linearizability.
This trade-off is known as the CAP theorem (Consistency, Availability, Partition tolerance — pick 2 of 3). However, DDIA is critical of CAP:
The real reason many systems avoid linearizability is not fault tolerance but performance. Attiya and Welch proved that linearizable reads and writes require response time proportional to the uncertainty of network delays. In networks with high variability, linearizability is inherently slow — this is not an implementation flaw, it's a theoretical bound.
Ordering helps preserve causality: cause comes before effect. Examples:
Causality defines a partial order: some events are causally related (one happens before another), but concurrent events are incomparable. Linearizability, by contrast, imposes a total order: every pair of operations has a defined order.
Causal consistency preserves the causal order without the cost of linearizability. It is the strongest consistency model that does not slow down due to network delays and remains available under network failures. Research systems (SwiftCloud, Bolt-on Causal Consistency) explore this, but it has not yet seen wide production adoption.
Tracking all causal dependencies explicitly is impractical (too many reads to track). Instead, we can use sequence numbers or logical clocks to order events.
A Lamport timestamp (1978) is a pair of (counter, node ID) that provides a total order consistent with causality. Each node tracks the maximum counter it has seen and includes it in every outgoing request. When receiving a request, a node advances its counter to the max value seen. This ensures that if A causally precedes B, then A has a lower Lamport timestamp than B.
However, Lamport timestamps have a critical limitation: they cannot tell you whether two operations are concurrent or causally dependent — only that there is a total order. Moreover, timestamp ordering is not sufficient for problems like uniqueness constraints. To know that your username registration succeeded, you need to know that no other node is concurrently registering the same name. Lamport timestamps cannot provide this — the total order only emerges after all operations are collected. You need total order broadcast.
Total order broadcast (also called atomic broadcast) solves the problem of getting all nodes to deliver the same messages in the same order. It guarantees two safety properties:
Total order broadcast is equivalent to state machine replication: if every replica processes the same writes in the same order, they stay consistent. It is also how ZooKeeper and etcd work internally.
To implement a linearizable compare-and-set (e.g., for unique usernames):
Since all nodes deliver messages in the same order, they all agree on which claim was first. This gives linearizable writes. For linearizable reads, you can sequence reads through the log, query the log position, or read from a synchronously updated replica.
It can be proved that these problems are all equivalent — solving one gives you a solution for all:
Atomic commit across multiple nodes requires consensus. The classic algorithm is two-phase commit (2PC). Do not confuse 2PC with 2PL — 2PC provides atomic commit; 2PL provides serializable isolation.
2PC involves a coordinator (transaction manager) and participants:
The key invariants:
If the coordinator crashes after receiving "yes" votes but before sending commit/abort, participants are in doubt. They cannot unilaterally commit (another participant may have aborted) or abort (the coordinator may have decided commit). The only solution is to wait for the coordinator to recover and read its transaction log. This is why 2PC is a blocking atomic commit protocol. In practice, in-doubt transactions can hold locks for minutes or hours, blocking other work.
Three-phase commit (3PC) tries to fix the blocking problem but requires bounded delays — unrealistic in most systems. Nonblocking atomic commit requires a perfect failure detector, which timeouts cannot provide in an asynchronous network.
X/Open XA is a standard for implementing 2PC across heterogeneous technologies (different databases, message brokers). It is supported by PostgreSQL, MySQL, Oracle, SQL Server, ActiveMQ, etc. XA is a C API (with Java bindings via JTA) — the coordinator is typically a library in the application process.
XA has serious operational problems:
Trade-off: database-internal distributed transactions (VoltDB, MySQL Cluster NDB) can work well because they use a single optimized protocol. Heterogeneous XA transactions cross system boundaries and are much harder — they are the lowest common denominator, and the coordinator is a single point of failure.
Formal consensus properties:
Termination is the liveness property (something good eventually happens). Agreement, integrity, and validity are safety properties (nothing bad happens) and must hold even under failures.
The FLP result (Fischer, Lynch, Paterson) proved that consensus is impossible in a fully asynchronous system model (no clocks, no timeouts) with even one crash-prone node. However, this does not mean consensus is impossible in practice — real systems use timeouts, failure detectors, and randomized algorithms, which escape the FLP bounds.
The best-known fault-tolerant consensus algorithms are Paxos, Raft, Zab (ZooKeeper), and Viewstamped Replication (VSR). Most implement total order broadcast directly (Multi-Paxos, Raft, Zab) rather than single-value consensus repeated.
All consensus protocols use a leader internally, but they do not guarantee the leader is unique. Instead, they define an epoch number (ballot number in Paxos, view number in VSR, term number in Raft) and ensure that within each epoch, the leader is unique.
When the current leader is suspected dead, nodes start a new election with an incremented epoch number. If a leader from an older epoch sends conflicting messages, the leader with the higher epoch number prevails.
Before a leader can decide anything, it must collect votes from a quorum (typically a majority). A node only votes for a proposal if it is not aware of any higher epoch. The key insight: the quorum for a leader election and the quorum for a proposal must overlap. This overlap ensures that if a proposal succeeds, at least one node that voted for it participated in the most recent election, guaranteeing that no newer leader can have been elected without knowing about the proposal.
| 2PC | Consensus (Paxos/Raft/Zab) | |
|---|---|---|
| Coordinator | Not elected; single fixed coordinator | Leader is elected via epoch voting |
| Votes needed | All participants must say "yes" | Only a majority quorum needed |
| Blocking | Yes — coordinator crash blocks all | No — leader failure triggers new election; safety preserved |
| Recovery | Manual / depends on coordinator log | Automatic via leader election + log replication |
ZooKeeper, etcd, and Consul are not general-purpose databases — they hold small amounts of data (fit in memory) and provide consensus-based coordination features:
| Feature | What it provides |
|---|---|
| Linearizable atomic operations | Compare-and-set for locks and leader election |
| Total ordering of operations | Monotonically increasing fencing tokens (zxid in ZooKeeper) |
| Failure detection | Heartbeat-based sessions; ephemeral nodes auto-deleted on session expiry |
| Change notifications | Watchers that push updates to clients when data changes |
These features are invaluable for work allocation: assigning partitions to nodes, detecting failures, rebalancing on node join/leave, and leader election. ZooKeeper runs on a small fixed set of nodes (3 or 5) and "outsources" consensus to itself — clients are many but the voting group is small.
Service discovery (finding which IP to connect to for a service) often does not require consensus — DNS with caching works well enough. However, if your consensus system already knows the leader, it can serve that information as a side effect.
Rule of thumb: if your problem reduces to one of the consensus-equivalent problems (leader election, uniqueness constraints, total order broadcast, distributed locking, atomic commit), use ZooKeeper/etcd rather than implementing your own algorithm. Consensus is notoriously hard to implement correctly — even expert implementers get it wrong.
Chapter 9 ends Part II of DDIA. The arc of Part II is:
Part III (Chapters 10-12) shifts from theory to practice: batch processing, stream processing, and the future of data systems.
1. What is the defining property of linearizability?
Once a read returns a value, all later reads must see that value or newer Replicas eventually converge to the same value Transactions behave as if executed in serial order2. What is the key difference between linearizability and serializability?
Linearizability is a single-object recency guarantee; serializability is a multi-object transaction isolation property Linearizability requires total order; serializability does not They are synonyms for the same guarantee3. Why is the CAP theorem of limited practical use according to DDIA?
It has narrow scope (only linearizability, only partitions) and provides little practical design guidance It is mathematically incorrect It perfectly captures all distributed systems trade-offs4. What does causal consistency preserve that eventual consistency does not?
Causal order: if A happened-before B, all nodes see A before B Linearizable reads and writes Total ordering of all operations5. What is the key limitation of Lamport timestamps for solving consensus problems like unique usernames?
They cannot finalize the total order at proposal time They cannot detect concurrent operations They are too large to transmit efficiently6. What two safety properties does total order broadcast guarantee?
Reliable delivery and totally ordered delivery Bounded latency and exactly-once delivery At-most-once delivery and causal ordering7. What critical problem makes 2PC a blocking protocol?
In-doubt participants cannot decide while the coordinator is down Network partitions cause all participants to abort Two-phase commit requires too many network round-trips8. How do consensus algorithms (Paxos/Raft) guarantee safety despite leader failures?
Epoch numbering and quorum overlap All nodes must vote on every proposal The leader persists every decision before responding9. What does the FLP result prove about consensus?
Consensus cannot be guaranteed in a fully asynchronous system with one crash-prone node Consensus is impossible in all distributed systems Consensus requires at least two-thirds of nodes to be non-faulty10. What is the relationship between total order broadcast, consensus, and linearizable compare-and-set?
They are all equivalent to each other Total order broadcast is strictly stronger than consensus Linearizable compare-and-set is easier than consensusEventual → replicas converge eventually
Causal → preserves happens-before order
Linearizable → single-copy illusion with real-time ordering
Recency guarantee: once a read returns V, all later reads see ≥ V
Operations appear atomic at some point between invocation and response
Single-object guarantee × (not transactions)
Required for: leader election, uniqueness constraints, cross-channel ordering
Linearizability → single-object recency, respects real-time
Serializability → multi-object transactions, any serial order OK
SSI = serializable but NOT linearizable (snapshot reads are stale by design)
Strict serializability = both combined
During network partition → choose linearizability (CP) or availability (AP)
DDIA critique: too narrow (only linearizability, only partitions), superseded
Real reason to avoid linearizability = performance, not fault tolerance
Attiya-Welch: linearizable R/W latency ≥ network delay uncertainty
Partial order: cause before effect. Concurrent ops are incomparable.
Causal consistency = preserves causal order without linearizability cost
Strongest model that avoids CAP trade-off
Captured via version vectors, Lamport timestamps
(counter, nodeID) — total order consistent with causality
Nodes propagate max counter seen on every request
Limitation: cannot finalize order at proposal time → need consensus
a) Reliable delivery → no lost messages
b) Totally ordered delivery → same order on all nodes
Equiv to state machine replication + consensus
Building linearizable storage: append to log, read log, check position
Coordinator + participants. Phase 1 = prepare. Phase 2 = commit/abort.
Commit point = coordinator writes decision to disk
Participant votes "yes" → surrenders right to abort
Coordinator crash → participants in doubt → blocking
XA = 2PC across heterogeneous systems (db, queue, etc)
Problems: coordinator SPOF, lock holding, manual recovery, amplifies failures
a) Agreement → all correct nodes decide same value
b) Integrity → no double decision
c) Validity → decision must be a proposed value
d) Termination → non-crashed nodes eventually decide
Safety (a,b,c) must hold always. Liveness (d) requires majority.
Async system → no deterministic consensus with even 1 crash-prone node
Escaped via timeouts, failure detectors, random numbers
All use epoch numbers + quorum overlap
a) Epoch (term/view/ballot) → unique leader per epoch
b) Leader election → incremented epoch + majority vote
c) Proposal → leader sends to quorum; overlap guarantees safety
d) 2PC needs ALL yes; consensus needs MAJORITY
a) Sync replication → slower than async
b) Strict majority → 3 nodes = tolerate 1 failure; 5 = tolerate 2
c) Fixed membership → dynamic membership harder
d) Network sensitive → flaky links cause leader churn, near-zero throughput
NOT general-purpose DBs. Small data, in-memory.
Provide: linearizable CAS, fencing tokens (zxid), sessions + ephemeral nodes, watchers
Use for: leader election, partition assignment, config coordination
"Outsource" consensus: tiny voting group (3 or 5 nodes), many clients
Rule: if problem reduces to consensus-equivalent class → use ZK/etcd, don't build your own
Primary source: Kleppmann, M. (2017).
Designing Data-Intensive Applications, Chapter 9: “Consistency and
Consensus.” O'Reilly Media.
Recommended supplements: Diego Ongaro's Raft thesis (the most understandable
consensus explanation), the ZooKeeper documentation, Kyle Kingsbury's Jepsen blog posts, and
the Google Spanner paper for TrueTime.
Ask follow-up questions to drill into: the formal definition of linearizability, how Raft handles log inconsistencies, why 2PC is blocking but Paxos is not, the quorum overlap proof, how ZooKeeper's atomic broadcast (Zab) works, or the difference between Lamport timestamps and version vectors.