Distributed Fundamentals¶
Tier: 1 (System Constraints)
Concepts: 14
Durability: Timeless (rooted in physical constraints of speed of light, network unreliability, and impossibility results from distributed systems theory)
Fundamental Tensions¶
| Tension | Description |
|---|---|
| Consistency vs. Availability | Network partitions are inevitable; when they occur, systems must choose between serving potentially stale data (availability) or refusing requests until partition heals (consistency). This tension is fundamental because information cannot propagate faster than light, and networks are physically unreliable. |
| Consistency vs. Latency | Even without partitions, achieving strong consistency requires coordination between nodes, adding round-trip time. This tension exists because synchronization requires communication, and communication takes time proportional to distance. |
| Safety vs. Liveness | Safety properties (nothing bad happens) can always be preserved by doing nothing; liveness properties (something good eventually happens) require action that risks safety. No system can guarantee both in the presence of failures - a mathematical impossibility. |
| Simplicity vs. Fault Tolerance | Handling failures requires additional mechanisms (retries, timeouts, fallbacks, consensus protocols), each adding complexity. Single points of failure are simple but fragile; redundancy is robust but complex. |
| Agreement vs. Progress | Reaching consensus requires waiting for participants, but waiting indefinitely prevents progress when participants fail. Every consensus protocol must balance waiting (for correctness) against timeouts (for progress). |
Concepts¶
- CAP Theorem
- PACELC Extension
- Fallacies of Distributed Computing
- Two Generals Problem
- FLP Impossibility
- Failure Mode Spectrum
- Partial Failure
- Absence of Global Time
- Logical Time and Causality
- Consensus Problem
- Quorum Systems
- Split Brain and Fencing
- Replication Trade-offs
- Idempotency as Fundamental Requirement
Cross-Domain Transfer Summary¶
| This Domain Concept | Transfers To |
|---|---|
| CAP Theorem | Database selection, cache design, microservices architecture, edge computing |
| PACELC Extension | Database tuning, replication strategy, globally distributed systems |
| Fallacies of Distributed Computing | Microservices, mobile apps, IoT, cloud architecture, API design |
| Two Generals Problem | Payment systems, order processing, network protocols |
| FLP Impossibility | Consensus protocol design, blockchain, distributed databases |
| Failure Mode Spectrum | Blockchain consensus, financial systems, critical infrastructure |
| Partial Failure | Error handling design, resilience engineering, chaos engineering |
| Absence of Global Time | Event ordering, conflict resolution, audit logs |
| Logical Time and Causality | Version control, collaborative editing, event sourcing, CRDTs |
| Consensus Problem | Distributed locks, atomic commit, configuration management |
| Quorum Systems | Distributed file systems, replicated state machines |
| Split Brain and Fencing | Cluster management, distributed locks, high availability |
| Replication Trade-offs | CDN design, cache strategies, disaster recovery |
| Idempotency | API design, payment systems, message queues, event-driven systems |
Canonical Sources¶
| Source | Coverage |
|---|---|
| Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System" (1978) | Logical time, happens-before, foundational ordering concepts |
| Fischer, Lynch & Paterson, "Impossibility of Distributed Consensus with One Faulty Process" (1985) | FLP impossibility, fundamental limits of consensus |
| Lamport, Shostak & Pease, "The Byzantine Generals Problem" (1982) | Byzantine failures, fault tolerance requirements |
| Brewer, "CAP Theorem" (2000); Gilbert & Lynch formalization (2002) | CAP theorem, consistency/availability trade-off |
| Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design" (2012) | PACELC, latency considerations |
| Deutsch, "Eight Fallacies of Distributed Computing" (1994) | Practical distributed systems pitfalls |
| Gray, "Notes on Data Base Operating Systems" (1978) | Two Generals, distributed transactions, idempotency |
| Waldo et al., "A Note on Distributed Computing" (1994) | Fundamental differences between local and distributed |
| Kleppmann, "Designing Data-Intensive Applications" (2017) | Modern synthesis of distributed systems concepts |
| Gifford, "Weighted Voting for Replicated Data" (1979) | Quorum systems |
| Helland, "Building on Quicksand" (2009) | Replication and consistency in practice |