Course · 08

How do many machines agree when the network can fail?

Once data lives on more than one machine, messages get lost, clocks disagree and machines pause. This page explains what you can and cannot promise, and the tools that make machines agree: quorums, Raft, fencing tokens, logical clocks and careful retries.

—Words you need

Each jargon word once, in plain words glossary

01The eight fallacies of distributed computing

Wrong beliefs that break real systems core

Peter Deutsch wrote seven of these at Sun around 1994. James Gosling added the eighth. Each one is a thing new engineers assume, and production disproves.

Silence is not an answer. Every design on this page exists because "no reply" has four possible meanings.

Source: Fallacies of distributed computing (secondary) · Rotem-Gal-Oz

02CAP, stated correctly, and PACELC

What you give up when the network splits interview favourite

CAP says: when a network partition happens (machines alive, but cut off from each other), a system must pick. Either it stays consistent (C, every read sees the latest write) and refuses some requests. Or it stays available (A, every working node answers) and may return old data.

Common misreadings:

• "Pick 2 of 3." Wrong. Partitions are not optional, so you never "pick CA" for a multi-machine system. The choice is C or A during a partition.
• "AP means never consistent." Wrong. With no partition, an AP system usually is consistent within milliseconds.
• CAP's C is linearizability, not the C in ACID (which means "rules like foreign keys hold").
• CAP's A is strict: every non-failing node must answer. A system that answers from the majority side only is "not available" in CAP terms, yet very usable.

PACELC (Daniel Abadi, 2012) adds the everyday case: if Partition, choose A or C; Else, choose Latency or Consistency. Even with a healthy network, waiting for replicas costs time.

Say it like this in interviews: "During a partition we choose; normally we trade latency for consistency." Then name which side your design picks and why.

Source: Gilbert & Lynch 2002 · Brewer 2012 · Abadi PACELC

03Consistency models on a timeline

Strong, sequential, causal, eventual, read-your-writes core

A consistency model is a promise about which values a read may return. Picture each operation as a bar from when it starts to when it finishes.

Stronger models are easier to program and cost latency and availability. Pick the weakest model your users won't notice.

Source: jepsen.io/consistency/models and its pages for linearizable, sequential, causal, read-your-writes, monotonic reads

04Consensus, and how Raft elects a leader

One leader per term, chosen by majority deep dive

Consensus means a group of machines agrees on one value, such as "who is leader" or "what is log entry 7", even if some crash. You need it for leader election, distributed locks and configuration. Heartbeats alone cannot do it safely.

Raft splits time into numbered terms. Each term has at most one leader. A follower that hears nothing for a random election timeout becomes a candidate, adds 1 to the term, votes for itself and asks the others.

• One vote per term. Each server votes for at most one candidate per term, first come first served. So two leaders in the same term is impossible.
• Random timeouts make split votes rare: usually one server times out first and wins before others start.
• Up-to-date check. A server refuses to vote for a candidate whose log is behind its own. So a new leader always has every committed entry.
• Higher term wins. An old leader that sees a higher term steps down at once.

Majority votes plus one vote per term make two leaders in one term impossible. That is the whole trick behind split-brain safety.

Source: Ongaro & Ousterhout 2014 · raft.github.io · Google SRE book, Managing Critical State

05Raft log replication, and Paxos in one paragraph

An entry is safe once a majority has it deep dive

The leader adds each client command to its log and sends it to followers (the AppendEntries message, which also works as the heartbeat). Once a majority has stored the entry, it is committed: it will never be lost. Then every server applies it to its state machine (for example, its key-value map).

Paxos in one paragraph. Paxos (Lamport) is the older consensus algorithm, with three roles: proposers, acceptors and learners. Phase 1: a proposer picks a number n and sends "prepare n"; acceptors promise to ignore lower numbers and report any value they already accepted. Phase 2: if a majority promised, the proposer sends "accept n, v", using the highest-numbered value already accepted if there is one. A value accepted by a majority is chosen. Raft gives the same safety but was designed to be easier to understand and build; Multi-Paxos plus a stable leader looks a lot like Raft.

Use 3 or 5 voters. 4 costs more than 3 and survives the same single failure.

Source: Raft paper · Paxos Made Simple · etcd FAQ

06Leader election in practice, locks and fencing tokens

Don't build consensus; borrow it interview favourite

You almost never write Raft yourself. You use a service that runs it: etcd (Raft, used by Kubernetes) or ZooKeeper (its own protocol, ZAB). Your app gets a lease or an ephemeral node, and whoever holds it is leader.

• ZooKeeper recipe: each candidate creates an ephemeral, sequential node (it vanishes when the session dies, and gets a growing number). Lowest number is leader. Each other node watches only the one just below it, so a leader death wakes one node, not all.
• etcd: the Go concurrency package offers locks and elections built on a lease that the client keeps alive.

But a lock alone is not safe. A client can pause (garbage collection, a slow disk) after getting the lock. Its lease expires, another client gets the lock, and then the first one wakes up and writes anyway.

A lock is a hint, not a guarantee. The resource you protect must check a fencing token, or a paused client will corrupt it.

Source: How to do distributed locking · ZooKeeper recipes · etcd FAQ

07Clocks: why "which came first?" is hard

Skew, NTP, Lamport, vector, hybrid clocks, TrueTime deep dive

Every machine has its own quartz clock, and they drift apart. NTP (Network Time Protocol) pulls them back toward a time server, but only to within some error. So "write A has timestamp 10:00:00.005, write B has 10:00:00.003" does not prove B happened first.

The fix is to order events by cause, not by wall time. Lamport's rule: keep a counter. Add 1 before each event. Send the counter with each message. On receive, set counter = max(mine, message) + 1.

Never decide "which write came first" by wall clock alone. Use logical counters, vector clocks for conflicts, or bounded uncertainty plus waiting.

Source: RFC 5905 · Lamport 1978 · HLC, Kulkarni et al. 2014 · Spanner, OSDI 2012 · CockroachDB transaction layer

08Two-phase commit and why it blocks

Atomic writes across machines, at a price interview favourite

Two-phase commit (2PC) makes a transaction across several databases all-or-nothing. Phase 1: the coordinator asks each participant "prepare": write everything durably, keep locks, and vote yes or no. Phase 2: if all said yes, it sends "commit"; otherwise "abort".

2PC gives atomicity and costs availability. In microservices, prefer sagas or the outbox pattern unless you truly need all-or-nothing.

Source: Gray & Lamport · PostgreSQL docs

09Idempotency and the exactly-once myth

You can't stop duplicates; you can make them harmless core

When a reply is lost, the client retries. The server may have done the work already. So over a network you can choose at-most-once (never retry, may lose) or at-least-once (retry, may duplicate). True exactly-once delivery is impossible in general.

What you can get is exactly-once effect: at-least-once delivery plus idempotent processing, so a duplicate changes nothing.

POST /payments
Idempotency-Key: 8f1c2a7e-...      # same key on every retry
{"amount": 1000, "currency": "INR"}
# server: INSERT key UNIQUE; if it already exists, return the stored response

Say "effectively once": at-least-once delivery plus idempotent handlers. Anyone promising more has a narrow scope in the small print.

Source: Kafka design: delivery semantics

10Failure detection, retries, and fault types

Heartbeats, phi accrual, backoff with jitter core

A node is suspected dead when its heartbeats stop for longer than a timeout. A fixed timeout is a guess: too short gives false alarms during a GC pause, too long gives slow recovery.

The phi accrual detector learns the normal gap between heartbeats and outputs a suspicion number, phi, instead of yes/no. Higher phi means "more surely dead". You pick the threshold.

Retries must back off. If 1,000 clients all retry after exactly 1 second, they hit the recovering server together (a "thundering herd"). Exponential backoff doubles the wait each try; jitter picks a random wait up to that limit, spreading clients out.

# Full jitter
sleep = random_between(0, min(cap, base * 2 ** attempt))
# Equal jitter
temp = min(cap, base * 2 ** attempt); sleep = temp/2 + random_between(0, temp/2)
# Decorrelated jitter
sleep = min(cap, random_between(base, sleep * 3))

Fault types. Everything on this page assumes crash faults: nodes stop or go slow, but never lie. Byzantine faults are nodes that send wrong or malicious messages; tolerating f of them needs at least 3f + 1 nodes, which is why blockchains, not databases, pay that cost.

Timeouts guess, phi accrual guesses better. Always cap retries, back off exponentially and add jitter, and only retry idempotent calls.

Source: Exponential Backoff And Jitter · Builders' Library: timeouts, retries, backoff · Akka · cassandra.yaml

—When to use what

Situation, pick, why decision table

—Common mistakes

Things that sound right and are wrong traps

—Interview questions

20 questions, easy to hard, with model answers practice

—Cheat sheet

Numbers and facts to remember memorise

—Sources

All checked 2026-10-25 references