Distributed Systems Theorems & Fallacies

← Back to Domain-Specific Families

Abstractions about fundamental trade-offs, false assumptions and resource models in distributed and parallel computing — consistency-availability theorems (CAP, PACELC, strong consistency), the classic fallacies of distributed computing (reliable network, zero latency), shared-memory consistency and architecture (release consistency, cache-only memory), and failure modes such as split-brain.

19 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Cache-Only Memory Architecture — Make distributed node-local main memories cache-like, home-free stores that migrate and replicate shared data according to demand.
• CAP Theorem — A distributed data store cannot guarantee consistency and availability at once during a network partition, and since real networks always partition, the architect must choose which to sacrifice when one strikes.
• CAP Theorem (and variants) — Characterize any replicated data store by its coordinates on a small set of axes — the forced C-versus-A choice under partition, PACELC's latency-versus-consistency choice at rest, plus granularity dials and the CRDT merge-algebra escape.
• Carrier-Sense Multiple Access — A shared-medium access method in which stations sense an existing transmission and defer when the channel appears busy.
• Fallacy of Homogeneous Networks — The implicit assumption that all nodes, links, OSes, versions, and configs across a distributed deployment are uniform — a missing degree of freedom in the system's model of its substrate that stays latent until deployment crosses a boundary where the uniformity breaks.
• Fallacy of Stable Topology — The design-time assumption that a distributed system's addressing and routing graph stays fixed over an interaction's lifetime — dropping the time argument from G(t) — so every cached reference becomes a latent bet that its referent has not moved.
• Fallacy of the Reliable Network — The design-time error of programming a best-effort channel whose packet-loss probability is positive as if it were zero — assuming every message is delivered, ordered, and never dropped, reordered, or duplicated.
• Fallacy of Zero Latency — The design-time assumption that a remote call returns as fast as a local one, dropping the per-hop round-trip term L from the cost function, so that an operation making n network calls is budgeted as free when it actually costs at least n·L and compounds under sequential fan-out.
• Feature Envy — Flag a method whose cross-class field and method accesses to another class outnumber accesses to its own, signalling that the behavior lives at the wrong address and should be relocated to the class whose data it operates on.
• Floyd's Cycle-Finding Algorithm — A constant-extra-space method that advances two references at one and two steps along the same successor chain to detect a reachable cycle.
• MapReduce — A distributed-computation model that processes oversized datasets in two stages — a stateless map over each record and a key-scoped associative reduce — so that once the programmer honours that contract, the runtime handles parallelism, fault tolerance, and locality, with the shuffle as the single cost-governing synchronization point.
• Memory Management — The policy and machinery by which a running program acquires regions of a finite address space at the point of use and safely releases them once no longer reachable or owned — bridging the gap between logic-driven allocation and reachability-driven reclamation against a memory budget.
• Memory Rank — Group DRAM devices behind one chip-select so they activate together and contribute parallel bit lanes to one logical data-width unit on a memory channel.
• PACELC Theorem — Classify a replicated data system by two regime-dependent trade-offs — availability vs. consistency under Partition, and Else (normal operation) latency vs. consistency — into a four-letter posture from which its workload behaviour reads directly.
• Postel's Law (Robustness Principle) — Postel's protocol-design maxim — be conservative in what you send, liberal in what you accept — which keeps a multi-vendor system interoperable by having every implementation produce tightly to spec while its acceptance window absorbs the realistic scatter of others.
• Release Consistency — Release consistency relaxes ordinary shared-memory ordering while enforcing specified acquire/release synchronization boundaries for correctly labeled concurrent programs.
• Split-Brain Problem — The distributed-systems failure where a network partition splits a replicated cluster into subsets that each elect themselves as write authority and accept divergent writes; guard against it by enforcing that at most one subset — the quorum majority — may write.
• Strong Consistency — Guarantee that every read of a replicated store reflects the most recently completed write and all clients see one real-time-consistent total order (linearizability), so the system can be reasoned about as a single copy — bought with a coordination round and partition-time unavailability.
• Sun–Ni Law — Estimate scaled parallel speedup when usable memory capacity bounds workload growth, with Amdahl and Gustafson recovered as special choices of an application-specific growth factor.