Distributed Systems
A distributed system is a collection of independent computers that appears to its users as a single coherent system. This seemingly simple definition conceals decades of research, thousands of papers, and some of the hardest problems in computer science.
This section doesn't just describe distributed systems — it takes you from the fundamental impossibility results (FLP, CAP) through the algorithms that work around them (Raft, Paxos, CRDTs) to the engineering decisions you'll make when building real systems.
Why Distributed Systems Matter
Every production system you build will be distributed. The moment you have:
- A web server talking to a database → distributed system
- Two services communicating over HTTP → distributed system
- A cache layer between your app and storage → distributed system
- A read replica for your database → distributed system
You cannot escape distribution. You can only choose whether to understand it or be surprised by it.
The Eight Fallacies
In 1994, Peter Deutsch and James Gosling identified assumptions that developers make about distributed systems that are all false:
- The network is reliable — packets drop, connections reset, cables get cut
- Latency is zero — every network call adds milliseconds to seconds
- Bandwidth is infinite — you can saturate any link with enough traffic
- The network is secure — every byte traversing the network can be intercepted
- Topology doesn't change — nodes join, leave, and fail constantly
- There is one administrator — multiple teams, multiple policies, multiple agendas
- Transport cost is zero — serialization, deserialization, encryption all cost CPU
- The network is homogeneous — different hardware, OS versions, protocol versions
Every decision in this section traces back to these realities.
Concept Map
graph TB
FLP[FLP Impossibility] --> Consensus
CAP[CAP Theorem] --> Tradeoffs[Consistency vs Availability]
Consensus --> Paxos
Consensus --> Raft
Consensus --> BFT[Byzantine Fault Tolerance]
Paxos --> Raft
Tradeoffs --> Strong[Strong Consistency]
Tradeoffs --> Eventual[Eventual Consistency]
Strong --> TwoPC[2PC / 3PC]
Strong --> Raft
Strong --> LeaderElection[Leader Election]
Eventual --> CRDTs
Eventual --> Gossip[Gossip Protocols]
LeaderElection --> DistLocking[Distributed Locking]
LeaderElection --> ExactlyOnce[Exactly-Once Semantics]
CRDTs --> MergeFunction[Merge Functions]
Gossip --> FailureDetection[Failure Detection]
Time[Time & Ordering] --> Lamport[Lamport Timestamps]
Time --> Vector[Vector Clocks]
Time --> ExactlyOnce
Replication --> Strong
Replication --> Eventual
ConsistentHashing[Consistent Hashing] --> Replication
Snapshots[Global State] --> ChandyLamport[Chandy-Lamport]
style FLP fill:#ff6b6b,color:#fff
style CAP fill:#ff6b6b,color:#fff
style Raft fill:#51cf66,color:#fff
style Paxos fill:#51cf66,color:#fff
style CRDTs fill:#51cf66,color:#fff
style ExactlyOnce fill:#339af0,color:#fff
style Replication fill:#339af0,color:#fff
style LeaderElection fill:#339af0,color:#fff
Learning Path
Take it as a course
The Distributed Systems Course walks these pages as nine modules with lesson-by-lesson progress tracking.
Follow this order for the most coherent understanding. Richer than any single course — covers theory, algorithms, and production patterns.
Part 1 — Foundations
The theorems and models that shape every design decision.
| Order | Topic | Why This Order |
|---|---|---|
| 1 | System Models, Failure Models & Correctness | What every algorithm assumes about timing and failures — and safety vs liveness |
| 2 | CAP Theorem | The foundational trade-off — consistency vs availability during partitions |
| 3 | Consistency Models | What "consistent" actually means — strong, causal, eventual, and everything between |
| 4 | FLP Impossibility | Why consensus is impossible in async systems — and how real protocols escape it |
Part 2 — Data Distribution
How data gets spread across nodes and kept in sync.
| Order | Topic | Why This Order |
|---|---|---|
| 5 | Replication | Single-leader, multi-leader, leaderless — the full spectrum with trade-offs |
| 6 | Quorums & Leaderless Replication | W + R > N, sloppy quorums, hinted handoff, read repair and Merkle-tree anti-entropy |
| 7 | Consistent Hashing | How to partition data across nodes with minimal reshuffling |
Part 3 — Consensus & Coordination
The algorithms that let distributed nodes agree on things.
| Order | Topic | Why This Order |
|---|---|---|
| 8 | Replicated State Machines | Consensus + a log + a deterministic state machine — the pattern behind etcd, ZooKeeper and Spanner |
| 9 | Distributed Transactions | 2PC, 3PC, Sagas — coordinating writes across service boundaries |
| 10 | Paxos | The original consensus algorithm — theory every engineer should know |
| 11 | Leader Election | Bully, Ring, Raft election, ZooKeeper — and how to avoid split-brain |
| 12 | Leases & Fencing | Time-bounded authority and the tokens that stop a paused ex-leader from doing damage |
| 13 | Distributed Locking | Mutex semantics over a network — fencing tokens, Redlock, and why it's hard |
Part 4 — Time & Order
Why clocks lie and how to order events without them.
| Order | Topic | Why This Order |
|---|---|---|
| 14 | Clock Synchronization | NTP, PTP, TrueTime — and why you still can't trust wall clocks |
| 15 | Vector Clocks & Lamport Timestamps | Causal ordering of events without synchronized clocks |
| 16 | Causality & Version Vectors | Version vectors vs vector clocks, siblings, and dotted version vectors |
| 17 | Exactly-Once Semantics | Idempotency, transactional outbox, Kafka EOS — the hardest messaging guarantee |
Part 5 — Failure & Recovery
How nodes detect, gossip about, and recover from failures.
| Order | Topic | Why This Order |
|---|---|---|
| 18 | Failure Detectors | Φ-accrual, heartbeats, timeouts — how nodes know when peers are dead |
| 19 | Gossip Protocols | Epidemic information spreading — membership, failure detection at scale |
| 20 | Distributed Snapshots | Chandy-Lamport — capturing consistent global state of a running system |
Part 6 — Advanced Theory
The deep end — CRDTs, Byzantine failures, probabilistic structures.
| Order | Topic | Why This Order |
|---|---|---|
| 21 | CRDTs | Data structures that merge without conflicts — the elegant alternative to locking |
| 22 | Byzantine Fault Tolerance | When nodes can lie — PBFT, PoW, the 3f+1 requirement |
Part 7 — Practical Tools
Applied patterns you'll use daily in production.
| Order | Topic | Why This Order |
|---|---|---|
| 23 | Timeouts, Retries, Backoff & Hedging | Calling an unreliable network without causing a retry storm |
| 24 | Serialization & Wire Formats | JSON, Protobuf, Avro, Thrift — and evolving schemas safely |
| 25 | Cryptography Primer & PKI | Hashes, MACs, signatures, certificates and mTLS between services |
| 26 | Rate Limiting | Token bucket, sliding window, Redis-based distributed enforcement |
| 27 | Circuit Breaker | Failure isolation — preventing cascading failures across services |
| 28 | Bloom Filters | Probabilistic set membership — space-efficient duplicate detection |
| 29 | Queueing Theory | Little's Law, M/M/1 queues — the math behind capacity planning |
Part 8 — Landmark Systems
The systems and papers that defined the field — read them once you know the theory.
| Order | Topic | Why This Order |
|---|---|---|
| 30 | Landmark Systems Overview | How the eight systems relate and what each one taught the industry |
| 31 | GFS & HDFS | A master, chunk servers and a relaxed consistency model for huge files |
| 32 | MapReduce & Spark | Batch computation over GFS-style storage, then lineage and in-memory DAGs |
| 33 | Bigtable & HBase | A sorted, sparse map on SSTables — the wide-column store pattern |
| 34 | Amazon Dynamo | Always-writable leaderless storage — consistent hashing, quorums, vector clocks |
| 35 | ZooKeeper | Coordination as a service — znodes, watches, sessions and lock recipes |
| 36 | Spanner & TrueTime | Externally consistent global transactions with bounded clock uncertainty |
| 37 | Calvin & FaunaDB | Agree on the order first, then execute — deterministic transactions |
| 38 | Distributed Ledgers | Shared state among parties who don't trust each other — and when not to use one |
Key Insight
The entire field of distributed systems can be reduced to one question:
How do we get multiple machines to agree on something when any of them can fail at any time, messages can be lost or delayed, and there is no shared clock?
Every algorithm, every protocol, every pattern in this section is an answer to some aspect of this question, each making different trade-offs about what guarantees it provides and what it gives up.