Distributed Systems Foundations

11 canonical primitives for distributed systems theory. Each primitive resolves a specific correctness or availability failure. Primitives are domain-agnostic: the same quorum math that governs database replication governs agent-state synchronisation; the same fencing tokens that prevent split-brain in a storage cluster prevent double-writes in a payment processor.

When to Apply

Apply distributed-systems primitives when:

• 2+ nodes participate in a write or shared state (replication, consensus)
• Network partitions are possible and must be tolerated (CAP/PACELC tradeoff)
• Idempotency, exactly-once, or fencing tokens are needed for safety
• Consistency level is being chosen (linearizable / sequential / causal / eventual)
• Multi-region or multi-AZ deployment with failover/quorum requirements

Skip and use simpler alternatives when:

• Single-node system, single writer — none of these primitives apply
• Question is about throughput/latency under load — use foundations-queueing-theory
• Question is about availability/SLO budget — use foundations-reliability-theory
• "We don't have a partition problem" — verify by looking at past incidents; if true, simpler replication patterns suffice
• Eventual-consistency is acceptable AND ordering doesn't matter — use last-writer-wins or CRDTs without consensus
• Strong-consistency demand is a vague preference, not a stated business invariant — challenge it; the cost is high

Contents

• Quick Reference
• Primitive Index
• Formal Supporting Theory
• Misuse Boundaries
• Decision Checklist
• Anti-Patterns
• Expert Diagnosis: Reading Symptoms
• Consistency Level by Product Feature
• The Retry/Timeout/Idempotency Triad
• Most Outages Are Operational, Not Algorithmic
• Testing: Deterministic Simulation and Fault Injection
• Composition Recipes
• Workflow
• ASCII Flow
• Related Skills
• Fact-Checking

---

Quick Reference

#	Primitive	When to Reach For It
1	CAP / PACELC	Choosing a replication topology or data store trade-off
2	FLP Impossibility	Reasoning about whether a consensus protocol can terminate
3	Paxos	Implementing or auditing a quorum-based agreement protocol
3a	DAG-BFT Consensus (Shoal++/Mysticeti family)	BFT domains where every-node-proposes throughput and low latency are both required
4	Raft	Leader-based consensus; easier to implement than Paxos
5	Vector Clocks / Lamport Timestamps	Causal ordering of events across nodes
6	CRDTs	Conflict-free eventually-consistent data structures
7	Idempotency	Exactly-once semantics over at-least-once delivery
8	Leases and Fencing	Split-brain prevention; safe leader handover
9	Quorums (NWR)	Tuning read/write consistency vs. availability
10	Causal Consistency	Preserving happens-before across replicas without serialisability
11	Broadcast Protocols	Gossip, total-order broadcast, atomic broadcast, and inter-cluster consistent broadcast

---

Primitive Index

Each primitive has a full playbook in assets/templates/distributed-systems/.

#	Primitive	Failure Mode It Addresses
1	CAP / PACELC	Confusion between consistency, availability, and partition tolerance; latency vs. consistency under normality
2	FLP Impossibility	Expecting a deterministic consensus protocol to always terminate with one crash faulty node
3	Paxos	Leaderless agreement fragility; unbounded dueling proposers
3a	DAG-BFT Consensus	Throughput/latency tradeoff in Byzantine-adversarial, every-node-proposes settings
4	Raft	Unclear log divergence; leader ambiguity during network partition
5	Vector Clocks / Lamport Timestamps	Wall-clock ordering of events that may be concurrent
6	CRDTs	Merge conflicts in eventually-consistent replicated state
7	Idempotency	Duplicate delivery of at-least-once messages causing double processing
8	Leases and Fencing	Multiple nodes simultaneously believing they hold a lock (split-brain)
9	Quorums (NWR)	Stale reads or lost writes from uncoordinated replication
10	Causal Consistency	Reads seeing later writes before earlier causally-linked writes
11	Broadcast Protocols	Inconsistent replica state from unordered or lossy message delivery; see also DAG-BFT (#3a) for high-throughput ordered broadcast and C3B/Picsou for inter-cluster broadcast

3a. DAG-BFT Consensus

DAG-based Byzantine Fault Tolerant (BFT) consensus separates data dissemination from ordering: every node proposes blocks into a shared DAG structure, and a separate ordering rule determines the commit sequence. This eliminates the single-leader throughput bottleneck while tolerating Byzantine (arbitrary) faults.

When to reach for it: Byzantine-adversarial settings (blockchain/DeFi infrastructure, permissioned ledgers with untrusted validators) where every-node-proposer throughput is required AND low latency must be preserved.

Kill criteria: Drop if the workload is crash-fault-only — Raft (#4) is simpler and sufficient. DAG-BFT complexity is justified only when both high throughput and Byzantine fault tolerance are required.

DAG-BFT lineage: Narwhal/Tusk (EuroSys 2022, arXiv:2105.11827) introduced the DAG-mempool architecture separating dissemination from ordering; Bullshark (CCS 2022) added zero-overhead ordering on the DAG; Shoal++ (NSDI 2025) redesigned the commit rule for lower latency; Mysticeti (NDSS 2025) reached the 3-message-round lower bound.

Current state-of-the-art:

• Shoal++ (NSDI 2025): Redesigned commit rule reduces average commit latency from 10.5 to 4.5 message delays (60% reduction) while matching state-of-the-art DAG throughput. Successor to Bullshark/Shoal. Reference: Arun et al. 2025.
• Mysticeti-C (NDSS 2025, arXiv:2310.14821): First uncertified DAG BFT protocol to achieve the 3-message-round latency lower bound. WAN commit latency 0.5 s at >200 k TPS; 4× latency reduction on Sui production deployment. Fast path variant Mysticeti-FPC weaves certificates into the DAG without additional round trips. Reference: Babel, Chursin, Danezis, Kokoris-Kogias, Sonnino et al. 2025.

Trap: DAG-BFT benchmarks compare against prior DAG protocols (Bullshark, Shoal) with industry interest from protocol authors (Aptos Labs, MystenLabs). Claims about throughput/latency are self-reported; verify against your own workload and fault assumptions.

Trusted-network shortcut (2026): In a single data centre where the network itself can be trusted, the signature overhead that makes BFT expensive can be shed. SwitchBFT (NSDI 2026, Zeno, Ben-David, Silberstein) uses packet source authentication to eliminate cryptographic signatures on the fault-free path and programmable switches to enforce agreement and check safety, reaching the speed of NOPaxos (an in-switch crash-fault protocol). Kill criteria: the trust assumption is the whole design — it does not transfer to WAN, multi-tenant, or public-validator settings, where the DAG-BFT family above remains the right choice.

Cross-reference: DAG-BFT also functions as a high-throughput ordered broadcast variant — see primitive #11 (Broadcast Protocols).

Ordering fairness is a separate property from agreement. Consensus guarantees that replicas agree on an order, not that the order is fair. Where position in the total order has financial value (blockchain SMR, matching engines), a leader can front-run or sandwich without ever violating safety or liveness. Equal Opportunity (OSDI 2026, Zhang, Ni, Alvisi, van Renesse et al., Cornell) formalises this as a correctness condition distinct from the usual pair and shows bounded randomness — a Secret Random Oracle built on trusted hardware or threshold VRFs — mitigates ordering attacks at moderate latency cost. Treat "our consensus is safe" as saying nothing about ordering bias.

---

Formal Supporting Theory

Load references/formal-theory-map.md when the design depends on model assumptions: asynchronous vs. partially synchronous networks, happens-before and logical clocks, consensus safety/liveness, quorum intersection, broadcast ordering, CRDT semilattices, causal consistency, leases, fencing, or CAP/PACELC trade-off boundaries.

Misuse Boundaries

Load references/patterns-scenarios-traps.md before asserting a system is "exactly once", "available and consistent", "leader safe", "eventually consistent", or "CRDT-friendly". It contains production scenarios, anti-patterns, and the checks that prevent common distributed-systems folklore from becoming a false guarantee.

---

Decision Checklist

• Replication topology: Need to choose between availability and consistency during a partition? → CAP (#1)
• Latency vs. consistency under normal conditions: No partition, but need to understand the latency trade-off? → PACELC (#1)
• Consensus termination: Wondering whether your consensus protocol is guaranteed to terminate with a faulty node? → FLP (#2)
• Multi-node agreement without a stable leader: Need quorum-based agreement tolerant of proposer failures? → Paxos (#3)
• Leader-based replicated log: Need a simpler consensus protocol with strong leader semantics? → Raft (#4)
• Causal ordering of events: Need to determine if event A happened before event B across nodes? → Vector Clocks (#5)
• Conflict-free replication: Need replicas to converge without coordination? → CRDTs (#6)
• Exactly-once semantics: Using at-least-once delivery and need to prevent double processing? → Idempotency (#7)
• Lock / primary ownership safety: Need to prevent split-brain under GC pauses or network partitions? → Leases and Fencing (#8)
• Read/write consistency tuning: Need to choose R + W > N trade-offs for your replica set? → Quorums (#9)
• Causal visibility guarantees: Need to ensure writes are visible in causal order across replicas? → Causal Consistency (#10)
• Message dissemination: Need eventual or total-order delivery to all replicas? → Broadcast Protocols (#11)

---

Anti-Patterns

Anti-Pattern	Why It Is Wrong	Fix
Framing CAP as "pick 2 of 3"	CAP applies only during a network partition; C and A are not binary dials — they are contingent on partition occurrence. Under normal operation all three hold.	State the actual trade-off: during a partition you must choose consistency or availability. Use PACELC to reason about latency trade-offs when there is no partition.
Claiming "exactly once" delivery without idempotency	No transport layer provides exactly-once semantics end-to-end. At-least-once with deduplication is the only tractable pattern. Declaring exactly-once in the protocol interface creates a false contract.	Design receivers as idempotent. Use an idempotency key and a deduplicated state store (#7). Combine with at-least-once delivery.
Leader-only writes without fencing tokens	A deposed leader that has not yet learned about its demotion (e.g. due to a GC pause or a slow network) can continue to accept writes, causing split-brain corruption.	Issue a monotonically increasing fencing token with each lease (#8). Storage must reject writes with a stale token regardless of what the writer believes.
CRDTs with non-commutative operations	CRDTs guarantee convergence only when merge is commutative, associative, and idempotent. Encoding an operation that does not commute (e.g. subtract-then-add vs. add-then-subtract) breaks the convergence guarantee.	Model the state as a semilattice where merge is the join. Use G-Counter, PN-Counter, OR-Set, or LWW-Register depending on the operation set (#6).
Quorum reads without quorum write coordination	Reading from R replicas guarantees seeing the latest write only when R + W > N. Relaxing writes to W = 1 while reading from R = 1 means the latest value may never be in the intersection.	Set W and R such that W + R > N (#9). For strong consistency, use W = majority and R = majority.
Causal consistency without happens-before tracking	Relying on wall-clock timestamps to enforce causal order causes reads to see writes out of causal sequence when clocks drift.	Attach a vector clock or logical timestamp to every write (#5, #10). Readers use the vector clock to enforce causal order before exposing data.
Assuming Paxos/Raft guarantees liveness unconditionally	FLP proves that no deterministic consensus protocol can guarantee both safety and termination in an asynchronous network with even one crash fault. Liveness requires a partial-synchrony assumption.	Acknowledge the partial-synchrony assumption explicitly (#2, #3, #4). Add heartbeat and leader-election timeouts calibrated to the actual network model.
Single-leader bottleneck in read-heavy WAN workloads	Multi-Paxos and Raft route all reads through the leader, creating a bottleneck in read-heavy or geographically distributed workloads.	For balanced or read-heavy WAN workloads, consider Pineapple-style any-node serving (NSDI 2025): unifies Multi-Paxos with ABD atomic registers via logical timestamps, allowing any node to serve reads and writes with >50% median latency reduction vs. Raft. Preferred over EPaxos when tail latency matters (EPaxos Revisited, NSDI 2021, showed EPaxos tail latency is 4x worse than Multi-Paxos). Reference: Bantikyan et al. 2025. Kill criteria: drop in write-dominated workloads (extra round on write path) or if leader instability is not the bottleneck. Where replacing the protocol is not an option, Jetpack (OSDI 2026, Tang, Zhang, Shen, Shi, Mu) retrofits a 1-RTT fast path onto an existing consensus protocol — commands race the fast and original paths, and the original path is forced to honour whichever decision commits — cutting average commit latency by up to 60% across six systems in a 10-datacentre AWS deployment. Its stated hazard is the one to audit in any home-grown fast path: promises made during stable operation can silently become invalid across a view change.

---

Expert Diagnosis: Reading Symptoms

A non-expert asks "which primitive applies?" An expert reads a symptom report and already suspects a short list of mechanisms before opening any code — because most distributed-systems failures announce themselves through a small number of recognizable smells. Use this table to go from a bug report to a hypothesis before instrumenting anything.

Symptom	What It Smells Like	First Things to Check	Primitive
"We read the old value right after the write succeeded"	Read hit a replica that had not applied the write yet	Is W + R > N? Is the read sticky to the writer's replica or read-your-writes enforced? Did a load balancer route the retry to a different node than the original write?	Quorums (#9), Causal Consistency (#10)
"Two nodes both think they're primary" (split-brain)	A lease expired without the storage layer enforcing a fencing token, or a GC/scheduler pause exceeded the lease TTL without the holder noticing	Is the fencing token checked at the resource boundary (storage), not just in application logic? Was there a GC pause, VM stop-the-world, or container CPU throttle around the incident window that exceeds lease duration?	Leases and Fencing (#8)
"A write vanished after failover" (phantom write)	The client got an ack before a durable majority had the entry, or the failover promoted a replica that was not guaranteed to hold every committed entry	Does write-ack require majority acknowledgement before returning success? Does leader election enforce the up-to-date-log check (Raft's leader completeness) before granting votes? Or did the client treat a timeout as a definite failure and silently drop a write that actually committed?	Raft/Paxos (#3/#4), Idempotency (#7)
"Duplicate charge/email/row after a retry"	At-least-once retry without a stable idempotency key, or the key was regenerated by the server on each attempt instead of supplied by the client	Is the idempotency key client-generated and identical across retries of the same logical operation? Is the check-and-execute atomic (same transaction), not check-then-execute?	Idempotency (#7)
"Replicas never converge; state keeps drifting"	A non-commutative operation was modeled as a CRDT, or tombstones/version vectors are growing without garbage collection, or a receive path skipped the max merge step	Does every operation in the type's operation set actually commute? Is there a compaction/GC policy for tombstones? Is the vector clock merged (not overwritten) on every receive?	CRDTs (#6), Vector Clocks (#5)
"Retries made the outage worse, not better"	Retry storm / thundering herd: no backoff, no jitter, no circuit breaker, and the retries are hitting an already-degraded downstream	See The Retry/Timeout/Idempotency Triad below	Idempotency (#7)
"It worked in staging, fell over in prod under load"	Usually not a protocol bug — connection-pool exhaustion, a timeout set below real p99 latency, clock skew larger than the lease-safety margin assumed, or a config value (quorum size, TTL) changed without a capacity review	See Most Outages Are Operational, Not Algorithmic below	n/a — operational triage first
"Consensus looks stuck / no leader elected"	Could be a genuine network partition with no majority component, or could be a resource-exhaustion symptom (thread pool, disk fsync latency, connection limits) masquerading as a partition to the protocol's heartbeat mechanism	Check host-level resource saturation before assuming a network partition; a node that cannot fsync in time looks identical to a network-partitioned node from the protocol's point of view	FLP (#2), Raft/Paxos (#3/#4)

How an expert uses this table: match the symptom, form one falsifiable hypothesis, check the specific mechanism (not the whole subsystem), and only reach for the primitive's full playbook once the mechanism is confirmed. Treat this as triage, not diagnosis — confirm with logs/traces before changing production behavior.

---

Consistency Level by Product Feature

Non-experts default to "strong consistency, to be safe" or "eventual consistency, for speed," as if it were one global dial. An expert asks which consistency level the specific feature actually needs, because over-provisioning consistency costs latency and availability for no user-visible benefit, and under-provisioning it creates a business-visible defect.

Product Feature	Consistency Actually Needed	Why	Common Over/Under-Engineering Mistake
Bank balance / ledger entry	Linearizable or serializable on the write path	Double-spend or lost debit/credit is a direct financial and compliance failure	Using CRDTs or LWW on a balance field — merge semantics do not express "never go negative" or "never double-apply"
Inventory decrement (prevent oversell)	Strong consistency on the decrement (majority-quorum write or single-writer with fencing)	Overselling is visible to the customer and costly to unwind	Eventual consistency without a compensating reconciliation/refund path
Shopping cart contents	Causal or eventual (CRDT OR-Set)	Availability matters more than perfect ordering; "union of adds, tag-based remove" is the natural merge	Routing cart writes through a consensus protocol — unnecessary coordination cost
Like / view / upvote counters	Eventual (CRDT G-Counter/PN-Counter)	An approximate, eventually-accurate count is acceptable; users do not notice a few seconds of undercount	Coordinating counter increments through a leader — throughput bottleneck for no correctness gain
Social feed post + reply ordering	Causal consistency	"Reply before post" is a confusing, user-visible anomaly; global linearizability is not required, only happens-before	Wall-clock timestamp ordering — clock skew silently reorders causally related posts
Session / auth token validity check	Read-your-writes on the session, ideally linearizable on the revocation path	A stale "still valid" read on a just-revoked token is a security defect, not a UX nuisance	Caching token validity with a TTL longer than the incident-response requirement for revocation
Leaderboard / ranking display	Eventual consistency with periodic reconciliation	Real-time exact ranking is rarely a stated business requirement; coordination cost is high relative to user benefit	Recomputing rank transactionally on every score update
Distributed lock / leader election	Linearizable, consensus-backed (Raft/Paxos + fencing)	Lock safety is a correctness invariant (split-brain prevention), not a latency knob	Implementing a "good enough" lock with a TTL and no fencing token
Collaborative document editing	CRDT (RGA) or causal broadcast	Low-latency convergence under concurrent edits matters more than a single global order	Serializing all edits through one node — kills the "everyone can type at once" experience
Feature flags / config propagation	Eventual, bounded-staleness for normal flags; near-linearizable for a security kill-switch	Most flags tolerate seconds of propagation lag; an incident kill-switch does not	Treating all flags as needing the same propagation SLA — over-engineering routine flags, under-engineering the kill-switch

Judgment call: when a stakeholder states "we need strong consistency" as a preference rather than tracing it to one of the rows above (a stated business invariant — money, inventory, security), challenge it. The cost (latency, availability, engineering complexity) is real; the benefit for most product features is not.

---

The Retry/Timeout/Idempotency Triad

These three mechanisms must be designed as one decision, not three independent ones — changing any one changes the safety requirement of the other two.