Part I of Database Internals treats a database as a single process talking to a single disk. Part II removes that assumption: data now lives on several machines, each with its own clock, its own failures and its own partial view of the world. Everything that was free on one node (shared memory, a single ordering of events, knowing whether a function call completed) must be rebuilt out of messages that can be lost, delayed or duplicated.

The payoff is horizontal scalability and fault tolerance: you add nodes instead of buying a bigger box, and the system keeps serving when a node dies. The price is a new vocabulary and a set of algorithms that interviewers love, because they expose whether a candidate really understands failure.

Vertical versus horizontal scaling

Vertical scaling means giving one node more CPU, memory or disk. It is simple, keeps all the single-node guarantees, and runs out: the largest machine you can buy has a ceiling, and a single machine is a single point of failure.

Horizontal scaling means adding nodes and spreading data and work across them. It has no hard ceiling, but every operation that used to touch local memory now crosses a network, and Part II is the study of what that costs.

The vocabulary of Part II

Term	Meaning in this part
Node / process / replica	A participant in the algorithm; a replica is a node holding a copy of some data.
Link	A communication channel between two nodes. Links are modelled by what they may do to messages (lose, duplicate, reorder).
Clock	A source of time, either physical (wall clock) or logical (counters, vector clocks). Clocks on different nodes are never assumed to agree.
Failure model	The set of misbehaviours the algorithm must survive: crashes, dropped messages, or arbitrary (Byzantine) behaviour.
Synchrony	What the algorithm may assume about timing: bounded delays (synchronous), no bounds (asynchronous), or bounds that hold eventually (partially synchronous).
Safety	"Nothing bad happens": for example, two nodes never decide different values.
Liveness	"Something good eventually happens": for example, a decision is eventually reached.

Distributed algorithms are built for four purposes, and each chapter of Part II serves one or more of them:

• Coordination: one process supervises the actions of others (leader election, chapter 10).
• Cooperation: processes depend on each other to finish a task (distributed transactions, chapter 13).
• Dissemination: information reaches every interested node quickly and reliably (anti-entropy and gossip, chapter 12).
• Consensus: processes agree on a single value (chapter 14, and implicitly chapters 10 and 13).

How the chapters build on each other

Arrows mean "defines vocabulary or mechanisms the later chapter assumes". Chapter 8 feeds everything; chapter 14 consumes everything.

Chapter by chapter

Chapter 8, Introduction and Overview, sets the rules of the game. It explains why remote execution is not local execution with a longer wire, lists the fallacies engineers fall for, and defines the abstractions every later chapter relies on: link types (fair-loss, stubborn, perfect), the two generals' problem, the FLP impossibility result, synchrony assumptions and failure models. Later chapters use its definitions without re-explaining them.

Chapter 9, Failure Detection, answers the first practical question a node has: is my peer dead or just slow? Because an asynchronous system cannot distinguish the two, detectors trade accuracy for speed. Heartbeats, timeouts, the phi-accrual detector used by Cassandra and Akka, and gossip-based detection all appear here. Every algorithm afterwards assumes some detector exists.

Chapter 10, Leader Election, uses the failure detector to keep a single coordinator alive. The bully algorithm and its refinements (next-in-line failover, candidate/ordinary nodes), the invitation algorithm and the ring algorithm show the design space, and the chapter explains why safe election in the presence of partitions really needs consensus.

Chapter 11, Replication and Consistency, is the heart of the part. It covers why we replicate, the CAP trade-off, shared-memory consistency models (linearizability, sequential, causal), client-centric models (read-your-writes, monotonic reads), eventual consistency, tunable quorums and CRDTs.

Chapter 12, Anti-Entropy and Dissemination, deals with replicas drifting apart. Read repair, hinted handoff, Merkle trees and bitmap version vectors catch divergence after the fact; gossip protocols spread membership and state without a coordinator.

Chapter 13, Distributed Transactions, extends atomic commitment across nodes: two-phase commit, three-phase commit, Calvin's deterministic scheduling, Spanner's TrueTime, Percolator's snapshot isolation on Bigtable, and coordination-avoidance ideas such as RAMP.

Chapter 14, Consensus, closes the loop. Broadcast primitives (reliable, atomic), Paxos and its variants (Multi-Paxos, Fast Paxos, EPaxos, Flexible Paxos), Raft, and Byzantine fault tolerance (PBFT). Leader election and atomic commit are both consensus instances, which is why the chapter sits last.

Suggested reading order

1. Chapter 8 first, always. Its definitions of safety, liveness, synchrony and failure models are prerequisites for everything else.
2. Chapters 9 and 10 together. Failure detection and leader election are two halves of the same problem: detecting that a coordinator is gone and replacing it.
3. Chapter 11 next, and slowly. Consistency models are the most frequently misstated topic in interviews.
4. Chapter 12 follows naturally from eventual consistency: once you accept divergence, you need a repair mechanism.
5. Chapters 13 and 14 last. Both depend on leader election, replication vocabulary and the impossibility results from chapter 8. Short on time? Read 14 before 13: Raft and Paxos are asked far more often than three-phase commit.

Readers of Designing Data-Intensive Applications will find chapters 11 to 14 overlap with DDIA chapters 5, 8 and 9; Petrov goes deeper on algorithm mechanics, Kleppmann on consistency semantics.

What interviewers ask from this part

• Explain the difference between safety and liveness, then apply it: why can a system be safe but not live during a partition?
• Why is exactly-once delivery impossible, and how do systems get exactly-once effects anyway? (Chapter 8: at-least-once plus idempotence or deduplication.)
• How does a node know its peer has crashed? It does not. Candidates who say "with a timeout" are then asked what phi-accrual adds.
• What is split brain and how do you prevent it? Leader election with epochs or terms, fencing tokens and leases (chapter 10) plus majority quorums (chapter 14).
• Compare linearizability and eventual consistency; where does causal consistency sit? (Chapter 11.)
• Why does two-phase commit block, and how do Spanner or Calvin avoid or mitigate it? (Chapter 13.)
• Walk through Raft leader election and log replication, or explain Paxos in two phases. (Chapter 14.)
• Design a system that stays available across regions: the answer stitches together replication, quorum reads and writes, anti-entropy and conflict resolution from chapters 11 and 12.