Why Distributed Systems Are Hard
Networks lie, clocks drift, nodes die mid-sentence. The three failures that make "just add more servers" a much harder sentence than it sounds — with real production war stories.
A book-quality series for engineers, not a paper list. Starts at "why does consensus exist" — replication, time, and failure — and walks the entire lineage: 2PC, Paxos, Raft, Byzantine fault tolerance, the modern Paxos family (EPaxos, Flexible Paxos, Atlas, Caesar, OmniPaxos), how etcd/ZooKeeper/Spanner/CockroachDB actually use it, and the current research frontier — QuePaxa and Cloudflare's Meerkat. By the last article you can read an SOSP/OSDI/NSDI consensus paper without translation.
Why consensus exists in the first place — before any algorithm. Distributed systems, the replication problem, CAP done properly, and what comes after CAP.
Networks lie, clocks drift, nodes die mid-sentence. The three failures that make "just add more servers" a much harder sentence than it sounds — with real production war stories.
Why "just use a database" isn't enough. Single points of failure, the split-brain scenario walked through visually, and why replicas disagreeing is the whole ballgame.
Not "pick two." What Consistency, Availability, and Partition tolerance actually mean formally, the proof sketch, and the misconceptions that make most CAP explanations wrong.
CAP only talks about partitions — but most of the time your network isn't partitioned, it's just slow. PACELC fills the gap, and where the CAP framing actively misleads people.
There is no "now" in a distributed system. Physical and logical clocks, failure detection, and the impossibility result that explains why every consensus algorithm makes a specific compromise.
Clock drift, NTP's real limits, why you can't order events across machines by comparing timestamps, and Google's TrueTime as the pattern of bounding a limit instead of pretending it's zero.
Forget measuring time — track causality instead. The happens-before relation, the two-rule counter mechanism, and exactly what it can't tell you.
One counter per process instead of a shared counter — how vector clocks detect true concurrency exactly, and Amazon Dynamo's documented "vector clock explosion" problem.
Chandra & Toueg's unreliable failure detectors — completeness vs accuracy, the eight detector classes, and why "eventually strong" is exactly enough.
No deterministic algorithm can guarantee consensus in bounded time in an asynchronous system, even with one crash failure — and the three escape hatches every real algorithm uses.
The machinery consensus sits on top of — state machine replication, logs, quorums, and how a "read" can be made safe without asking everyone every time.
Agree on an ordered sequence of deterministic commands, not on data directly — matching final state follows as a mathematical guarantee.
The concrete append-only log behind SMR — entry anatomy, how logs diverge and get repaired, snapshotting, and how a new replica catches up.
The formal proof that any two majorities overlap — the single mathematical fact behind every anti-split-brain mechanism in this series.
Reading from "the leader" isn't automatically safe. Quorum reads, leader leases and their clock-skew danger, and Raft's read-index protocol.
Safety vs. liveness, leader election, atomic broadcast — and the two commit protocols that predate real consensus and explain exactly why they aren't enough.
The two formal property classes every algorithm is judged by — why safety is always unconditional and liveness can depend on weaker assumptions.
Bully and Ring as the classical baseline, why consensus-integrated election inherits safety from majority overlap, and randomized timeouts vs split-vote livelock.
SMR, log replication, and Total Order Broadcast are provably the same problem — the formal equivalence with consensus, in both directions.
Prepare/commit for atomic distributed transactions, and the fatal blocking problem when the coordinator dies after deciding but before announcing.
The pre-commit phase that fixes 2PC's blocking under crashes — and why it fails unsafely under real network partitions, finally motivating majority consensus.
The algorithms everything else is measured against: single-decree and Multi-Paxos, Viewstamped Replication, Raft end to end, and Zab.
Lamport's Part-Time Parliament and the allegory-driven publication history, plus the precise problem statement Paxos solves.
The full Prepare/Promise, Accept/Accepted protocol, with a worked example tracing exactly why competing proposers stay safe.
Amortizing Phase 1 across an entire log — how a stable leader appends new entries with just one round-trip.
Oki and Liskov's independently-developed, often-forgotten algorithm — views, primaries, and the same majority-overlap mechanism, again.
Understandability as a design goal, terms, node states, and the full RequestVote leader-election protocol.
AppendEntries, the log-matching property, the subtle current-term commitment rule, and the full State Machine Safety proof.
Epochs, zxids, and FIFO client order as a structural guarantee — closing Phase 5 with a comparison across all four algorithms.
When nodes don't just crash — they lie. The Byzantine Generals Problem, PBFT, and the modern BFT lineage that powers blockchains.
Agreement under actively lying participants — why majority overlap breaks, and the proven 3f+1 node threshold.
The first practical BFT protocol — pre-prepare/prepare/commit, all-to-all broadcast, and cryptographically verifiable view changes.
Fixing PBFT's O(n²) bottleneck with threshold-signature aggregation and a pipelined three-chain commit rule.
Immediate deterministic finality via round-based propose/prevote/precommit, plus slashing-based economic accountability.
Separating data dissemination from ordering to break the leader-bandwidth bottleneck every prior BFT protocol shared.
Where this series stops being "another Raft explainer." Leaderless consensus, flexible quorums, and the research lineage that leads directly to QuePaxa and Meerkat.
Any replica commits directly via dependency-graph ordering instead of a fixed leader — the fast path/slow path trade-off.
Paxos's two quorums only need to intersect, not both be majorities — asymmetric quorum sizing and grid layouts.
Lamport's own precursors to EPaxos — commutative-operation reordering and one-round-trip optimistic proposing.
Standby nodes that activate only on failure, and decomposing the monolithic leader role into independently-scalable pieces.
Applies Flexible Paxos's quorum-shrinking to EPaxos's leaderless setting — near-majority fast quorums plus synchronization.
Proactive ordering certificates instead of EPaxos's reactive conflict detection — fewer slow-path fallbacks under contention.
A production-grade library: decoupled pluggable leader election and first-class, safely-engineered reconfiguration.
Four specialized fixes — reconfiguration safety, leader fan-out, data/order separation, and randomization-based simplification.
How the algorithms show up in systems you already run — etcd, ZooKeeper, Consul, Kafka's KRaft, Kubernetes — and how Jepsen actually tests the claims.
A close-to-textbook Raft wrapped in MVCC, watches, and leases — the real engineering is in the storage/API layers on top.
The hierarchical znode namespace, ephemeral nodes, and the lock/election/discovery recipe library every later system echoes.
Two protocols for two jobs: Raft for the strongly-consistent catalog, gossip for scalable failure detection across thousands of agents.
Replacing the ZooKeeper dependency with Raft built directly into Kafka — metadata as just another partition log.
No separate database — etcd is the single source of truth, and the controller pattern is etcd's watch mechanism at cluster scale.
A proof is about the algorithm; Jepsen is about the code — injecting real partitions and clock skew to find implementation bugs.
Consensus stretched across continents. Spanner's TrueTime, CockroachDB's Multi-Raft, FoundationDB, TiDB/YugabyteDB, and the WAN-latency tricks that make it bearable.
Externally consistent transactions at planet scale — bounded clock uncertainty and commit-wait, backed by real atomic-clock hardware.
Hybrid Logical Clocks as a software-only substitute for TrueTime, and Multi-Raft sharding at the scale of millions of ranges.
A radically layered architecture — a minimal transactional core everything else builds on — plus deterministic simulation testing.
Wire compatibility with MySQL and PostgreSQL as a first-class architectural bet, on top of the same Raft-sharded storage pattern.
The speed-of-light latency floor, made explicit — and the quorum leases, follower reads, and geo-partitioning that work around it.
Why live membership changes can silently reintroduce split-brain, and Raft's joint-consensus fix for it.
The frontier, read paper-by-paper in a consistent format: problem, core idea, architecture, failure handling, performance, trade-offs. Ending at QuePaxa and Meerkat.
An eight-part framework — problem, why existing algorithms fail, core idea, architecture, failure handling, performance, trade-offs, production applicability — for reading any paper honestly.
Randomized asynchronous consensus with hedging delays and a multi-armed-bandit optimizer, matching Multi-Paxos throughput while surviving adversarial jitter.
An experimental global consensus service built on QuePaxa, every replica writable, tested across 330+ data centers for small high-importance control-plane state.
Twenty algorithms compressed into one master comparison table, plus a decision framework of honest questions rather than a ranked best-to-worst list.
Batch size, payload size, topology, and replica count each swing throughput numbers 5-10x — a checklist for reading any performance claim honestly.
Post-quantum Byzantine consensus, AI training coordination, verifiable consensus without trusted hardware, and the decentralization-latency tension no algorithm has escaped.
Where consensus is headed, and the payoff: build your own consensus algorithm, benchmark it against Raft, and walk away with a working mental map of the entire field.
Permissionless participation, probabilistic finality, proof of stake, slashing, and how classical Byzantine consensus transfers into blockchain systems.
A layered architecture for intermittent devices: small stable quorums, local safety, buffered telemetry, convergence, and explicit reconciliation.
A teaching implementation built from invariants: persistent votes, elections, prefix checks, commitment, repair, and adversarial tests.
The complete field reduced to seven questions and a practical framework for choosing, reading, and testing consensus systems.