Before you use this reference
This page is a lookup, not a tutorial. The explanations live in Distributed Systems Fundamentals, The CAP Theorem, Partitioning and Sharding, Replication and Consistency Models, Consensus and Leader Election, Failure Detection and Timeouts, and Clocks and Ordering.
The eight fallacies#
Full reference: Fallacies of distributed computing.
1. The network is reliable. 5. Topology doesn't change.2. Latency is zero. 6. There is one administrator.3. Bandwidth is infinite. 7. Transport cost is zero.4. The network is secure. 8. The network is homogeneous.CAP / PACELC decision#
During a partition: choose Consistency or Availability (CAP)Otherwise: choose Latency or Consistency (PACELC)| System behavior | CAP choice | Example |
|---|---|---|
| Refuses writes/reads until partition heals | CP | Leader requires majority ack |
| Accepts writes on both sides, reconciles later | AP | Quorum store, W+R <= N |
Partitioning#
Range partitioning: ordered keys, good for range scans, hot-partition risk with monotonic keysHash partitioning: even write spread, poor for range scansConsistent hashing: adding/removing a node remaps ~1/N of keys, not nearly all of themReplication#
Leader-based: synchronous -> stronger durability, higher latency asynchronous -> lower latency, replication lag risk
Quorum-based (Dynamo-style): N = total replicas, W = writes required, R = reads required W + R > N => every read overlaps the latest write| Consistency model | Guarantee |
|---|---|
| Strong (linearizable) | Every read reflects the latest acknowledged write |
| Eventual | Replicas converge given no further writes — no bound on when |
| Read-your-writes | A client always sees its own writes; others may lag |
Consensus and leader election#
Majority quorum: a new leader needs votes from > N/2 nodes.Only one side of any network partition can ever reach majority —this is what makes split-brain structurally impossible, not just unlikely.Full reference: Raft.
Failure detection#
Shorter timeout -> faster detection, more false positivesLonger timeout -> fewer false positives, slower detection
Fencing (STONITH): forcibly isolate a node believed failed BEFORE letting a new leader accept writes.Logical clocks#
Lamport timestamp: one counter, guarantees correct order for causally related events only.
Vector clock: one counter per node, additionally reveals genuinely concurrent (unrelated) events.Further reading#
- CAP theorem and PACELC design principle — the two trade-offs behind every row above.
- Raft Consensus Algorithm — the consensus protocol referenced in the leader-election section.
- Lamport timestamp and Vector clock — full definitions for the logical-clock section.
- Dynamo: Amazon's Highly Available Key-value Store — the quorum-replication model summarized above.