On this page

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:

  1. The network is reliable — packets drop, connections reset, cables get cut
  2. Latency is zero — every network call adds milliseconds to seconds
  3. Bandwidth is infinite — you can saturate any link with enough traffic
  4. The network is secure — every byte traversing the network can be intercepted
  5. Topology doesn't change — nodes join, leave, and fail constantly
  6. There is one administrator — multiple teams, multiple policies, multiple agendas
  7. Transport cost is zero — serialization, deserialization, encryption all cost CPU
  8. 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.

OrderTopicWhy This Order
1System Models, Failure Models & CorrectnessWhat every algorithm assumes about timing and failures — and safety vs liveness
2CAP TheoremThe foundational trade-off — consistency vs availability during partitions
3Consistency ModelsWhat "consistent" actually means — strong, causal, eventual, and everything between
4FLP ImpossibilityWhy 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.

OrderTopicWhy This Order
5ReplicationSingle-leader, multi-leader, leaderless — the full spectrum with trade-offs
6Quorums & Leaderless ReplicationW + R > N, sloppy quorums, hinted handoff, read repair and Merkle-tree anti-entropy
7Consistent HashingHow to partition data across nodes with minimal reshuffling

Part 3 — Consensus & Coordination

The algorithms that let distributed nodes agree on things.

OrderTopicWhy This Order
8Replicated State MachinesConsensus + a log + a deterministic state machine — the pattern behind etcd, ZooKeeper and Spanner
9Distributed Transactions2PC, 3PC, Sagas — coordinating writes across service boundaries
10PaxosThe original consensus algorithm — theory every engineer should know
11Leader ElectionBully, Ring, Raft election, ZooKeeper — and how to avoid split-brain
12Leases & FencingTime-bounded authority and the tokens that stop a paused ex-leader from doing damage
13Distributed LockingMutex 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.

OrderTopicWhy This Order
14Clock SynchronizationNTP, PTP, TrueTime — and why you still can't trust wall clocks
15Vector Clocks & Lamport TimestampsCausal ordering of events without synchronized clocks
16Causality & Version VectorsVersion vectors vs vector clocks, siblings, and dotted version vectors
17Exactly-Once SemanticsIdempotency, transactional outbox, Kafka EOS — the hardest messaging guarantee

Part 5 — Failure & Recovery

How nodes detect, gossip about, and recover from failures.

OrderTopicWhy This Order
18Failure DetectorsΦ-accrual, heartbeats, timeouts — how nodes know when peers are dead
19Gossip ProtocolsEpidemic information spreading — membership, failure detection at scale
20Distributed SnapshotsChandy-Lamport — capturing consistent global state of a running system

Part 6 — Advanced Theory

The deep end — CRDTs, Byzantine failures, probabilistic structures.

OrderTopicWhy This Order
21CRDTsData structures that merge without conflicts — the elegant alternative to locking
22Byzantine Fault ToleranceWhen nodes can lie — PBFT, PoW, the 3f+1 requirement

Part 7 — Practical Tools

Applied patterns you'll use daily in production.

OrderTopicWhy This Order
23Timeouts, Retries, Backoff & HedgingCalling an unreliable network without causing a retry storm
24Serialization & Wire FormatsJSON, Protobuf, Avro, Thrift — and evolving schemas safely
25Cryptography Primer & PKIHashes, MACs, signatures, certificates and mTLS between services
26Rate LimitingToken bucket, sliding window, Redis-based distributed enforcement
27Circuit BreakerFailure isolation — preventing cascading failures across services
28Bloom FiltersProbabilistic set membership — space-efficient duplicate detection
29Queueing TheoryLittle'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.

OrderTopicWhy This Order
30Landmark Systems OverviewHow the eight systems relate and what each one taught the industry
31GFS & HDFSA master, chunk servers and a relaxed consistency model for huge files
32MapReduce & SparkBatch computation over GFS-style storage, then lineage and in-memory DAGs
33Bigtable & HBaseA sorted, sparse map on SSTables — the wide-column store pattern
34Amazon DynamoAlways-writable leaderless storage — consistent hashing, quorums, vector clocks
35ZooKeeperCoordination as a service — znodes, watches, sessions and lock recipes
36Spanner & TrueTimeExternally consistent global transactions with bounded clock uncertainty
37Calvin & FaunaDBAgree on the order first, then execute — deterministic transactions
38Distributed LedgersShared 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.