gabrielmoreira 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.
- Timeout too short relative to real tail latency → the caller retries a request that was actually still in flight and would have succeeded. This is safe only if the receiver is idempotent (#7). Without idempotency, an aggressive timeout is a duplicate-processing generator.
- Retry without backoff and jitter → synchronized retries from many callers hit the downstream at the same moment it is already degraded, extending the outage (retry storm / thundering herd). This is the single most common way "adding retries for resilience" makes an incident worse instead of better.
- Idempotency without a retry policy → dead weight; nothing is retried, so the dedupe store protects against nothing. Idempotency is a precondition for safe retries, not a substitute for having a retry policy.
- Rule of thumb: set timeouts above the observed p99.9 of the operation under normal load (not the p50 or even p99 — tail latency during partial degradation is what triggers spurious timeouts), use exponential backoff with full jitter and a bounded max-attempts, and add a circuit breaker that fails fast once the downstream's error rate crosses a threshold — a fast, clear failure is better than a retry storm that prevents recovery.
- Cross-check: the idempotency key's dedupe-store TTL must exceed the maximum possible retry window (last retry attempt + its own timeout), or a very late retry will be treated as a new operation. See primitive #7 for the dedupe-store schema.
- Expert smell: "we added retries and things got worse" is almost always missing backoff+jitter+circuit-breaker, not a case for removing retries — the fix is usually to make the retry policy safer, not to remove the safety net.
Most Outages Are Operational, Not Algorithmic
Distributed-systems theory (CAP, FLP, consensus safety proofs) answers what is possible — it explains why certain guarantees cannot be had for free. It does not predict where the next incident comes from. Field experience and public postmortems (major cloud providers and infrastructure vendors routinely publish these) repeatedly show that the proximate cause of an outage is configuration drift, capacity exhaustion, a deployment or migration mistake, or human error during an operational change — not a violated algorithmic invariant in Paxos, Raft, or the CAP trade-off itself. The theory is what you use to diagnose the incident correctly; it is rarely the site of the actual bug.
Canonical worked example — AWS us-east-1, 20 October 2025 (official post-event summary). No consensus protocol failed. A latent race condition in DynamoDB's DNS automation did: two DNS Enactor processes ran concurrently, one stalled, the other applied a newer plan and then ran cleanup — deleting the plan the stalled Enactor had just written, leaving the regional endpoint with an empty DNS record. The cascade is the part worth studying, because each stage is a primitive in this skill failing operationally rather than algorithmically:
- Empty DNS record → DynamoDB unreachable. A control-plane automation bug, reachable only through a specific interleaving — the kind of thing deterministic simulation testing (below) exists to find.
- Recovery caused the second outage. With DynamoDB restored, EC2's DropletWorkflow Manager tried to re-establish leases with hundreds of thousands of hosts at once and hit congestive collapse — a textbook retry storm on a lease (#8) renewal path, not a lease-safety violation.
- Backlogged state propagation → NLB health checks failed → Lambda, ECS, EKS, STS, Redshift and 100+ services degraded. Ordinary broadcast/propagation (#11) starved of capacity.
The lessons generalise: the failure was in automation that manages the primitives; recovery load exceeded steady-state load and needed its own capacity plan and backoff (see the triad); and a regional dependency shared by 100+ services made a single control-plane fault systemic. None of it is fixed by a stronger consensus protocol.
Before reaching for a primitive to "fix" an incident, ask:
- Was a config value (quorum size, election/lease timeout, TTL, connection-pool limit) changed recently without a corresponding capacity or timing review?
- Was the failover path (leader election, promotion, DNS/service-discovery cutover) tested under the same load and network conditions as the actual incident, or only tested in isolation at low load?
- Is "consensus looks stuck" actually a network partition, or is it resource exhaustion (disk fsync latency, thread pool saturation, CPU throttling) that looks identical to a partition from the protocol's point of view (see the last row of the symptom table)?
- Did a routine dependency upgrade (client library, driver, OS, kernel network stack) silently change a timeout default, retry default, or connection-pooling behavior?
This does not mean the primitives in this skill are unnecessary — they are exactly what lets you tell the difference between "our fencing token enforcement has a real gap" (an algorithmic/design bug worth a primitive-level fix) and "the lease TTL was fine but a bad deploy exhausted the connection pool and everything downstream started timing out" (an operational bug that no amount of consensus theory would have prevented). Do the operational triage first; escalate to a primitive-level design change only when the operational explanation is ruled out.
Testing: Deterministic Simulation and Fault Injection
The primitives above are design-time reasoning. The failures that reach production are interleavings nobody enumerated — the AWS DNS Enactor race above is exactly the shape. Two techniques dominate current practice, and they answer different questions.
Deterministic simulation testing (DST) runs the real system under a simulated clock, scheduler, network, and disk, so every source of non-determinism is controlled and seeded. A failing run replays byte-for-byte from its seed, which converts the worst class of distributed bug — the one-in-ten-thousand interleaving — from unreproducible into a regression test. Pioneered in FoundationDB (and independently at AWS) around 2010; by 2026 it is the expected standard for new storage and coordination infrastructure, with TigerBeetle, WarpStream, Resonate, and Antithesis-tested systems among the adopters. Antithesis productised the approach with a hypervisor that deterministically simulates a container set and injects faults.
- Design cost is the real cost. DST requires all I/O, time, and concurrency to go through injectable interfaces. Retrofitting it onto a system with ambient
time.Now(), direct syscalls, and unstructured threads is a rewrite, not a test-harness addition. Decide early or accept you will not have it. - It finds what you simulate. A fault the simulator cannot generate (a real NIC corrupting one bit, a firmware-level disk lie) stays invisible. DST complements, does not replace, staging chaos testing against real hardware.
Black-box consistency checking (Jepsen, using the Elle isolation checker) attacks the other side: it makes no assumption about internal structure, drives a real cluster under real faults, and checks the observed history against a claimed consistency model. Use it to falsify vendor claims, including your own.
The 2025–2026 Jepsen reports are worth reading as a set, because the failure patterns repeat:
| System (report) | What it shows |
|---|---|
| MariaDB Galera Cluster 12.1.2 (Mar 2026) | The documented recommended configuration (innodb_flush_log_at_trx_commit=0) did not flush before acknowledging, so coordinated crashes silently lost committed transactions; setting it to 1 reduced but did not eliminate loss. Also lost updates (P4) and stale reads in healthy clusters, against a claimed "between Serializable and Repeatable Read". Lesson: a vendor's recommended defaults are a performance choice, not a durability guarantee — read what the flag actually does. |
| TigerBeetle 0.16.11 (Jun 2025) | The counter-example. Only two safety issues found, exceptional resilience to disk corruption across every replica, and Strong Serializability upheld — from a system built around DST from day one. Its own postmortem, "Fuzzer Blind Spots", is a candid account of what in-house fuzzing missed and external black-box testing caught. |
Rule: a consistency or durability claim that has never been checked by an adversarial external harness is a design intention, not a property. Ask which faults were injected, which model was checked, and whether the tested configuration is the one you actually deploy.
Composition Recipes
Multi-region writes
Goal: Accept writes in multiple regions with bounded staleness and no lost updates.
Stack:
- Quorums (#9) — set W = majority across region replicas; read repair on stale reads.
- Leases and Fencing (#8) — each region's write coordinator holds a time-bounded lease; fencing token prevents deposed coordinators from writing.
- Idempotency (#7) — idempotent receivers with per-operation idempotency keys tolerate retries across region failover.
- Causal Consistency (#10) — vector clocks track happens-before across regions; clients use sticky-session routing to avoid causal anomalies.
WAN replication latency on the critical path (2025): For workloads where standard geo-replicated 2PC blocks at the WAN replication boundary (latency dominated by WAN RTT), see Mako (OSDI 2025): speculative 2PC decouples transaction execution from replication, eliminating WAN RTT from client-visible latency while preserving strong consistency with bounded-abort guarantees. Requires idempotent re-execution on speculative abort (#7). Artifact: github.com/makodb/mako. Kill criteria: drop if workload tolerates eventual consistency (use CRDTs instead) or if speculative aborts are frequent (high-contention workloads make speculation expensive).
RSM-to-RSM links across regions: Use Cross-Cluster Consistent Broadcast (C3B) from Picsou (OSDI 2025) rather than raw replication bridges or ad-hoc dual-write patterns. C3B provides formal correctness guarantees; see primitive #11 for details.
When to add CRDTs (#6): If the shared state supports a commutative merge (e.g. counters, sets, last-write-wins register), replace quorum coordination with CRDT replication to eliminate coordination overhead entirely.
Inputs: N (total replica count across regions), W (write quorum size), R (read quorum size), lease duration (ms), latency SLO for writes (p99 ms), partition tolerance requirement (AZ-failure count), idempotency key schema. Rules: Strong consistency requires W + R > N; set W = ⌊N/2⌋+1 (majority) for write durability; set R = 1 for read-heavy paths if W = N; lease duration must be shorter than the SLO for detecting a deposed coordinator; use CRDT replication when state supports commutative merge and coordination overhead exceeds the latency SLO. Outputs: Recommended (N, W, R) tuple, lease duration, expected write p99 latency per region, maximum AZ-failure tolerance, flag indicating whether CRDT replacement is viable.
Exactly-once receiver
Goal: Deliver a message exactly once to application logic despite at-least-once transport semantics.
Stack:
- Idempotent receiver (#7) — application operation is idempotent by design (pure function of inputs, no hidden state mutation).
- Idempotency key + dedupe store — persistent log of processed keys; reject duplicates before executing.
- At-least-once delivery — transport retries until acknowledged; the receiver's idempotency makes retries safe.
When to add Raft (#4): If the dedupe store itself must be replicated, use a Raft-backed key-value store so the dedupe log survives node failures without split-brain.
Inputs: Idempotency key schema (operation type + client ID + sequence number), dedupe store type (in-memory / persistent / replicated), at-least-once transport (retry count, backoff policy), expected duplicate rate (%), required exactly-once guarantee scope (single node vs. cluster). Rules: Receiver must be a pure function of its inputs with no hidden state mutations; every operation must be looked up in the dedupe store before execution; duplicate = same key → return cached result, do not re-execute; dedupe store must outlive the longest possible retry window; if the dedupe store is replicated, use Raft-backed KV so the log is durable across node failures. Outputs: Idempotency key format specification, dedupe store schema (key → result + TTL), confirmation that the receiver is side-effect-free, recommended dedupe TTL relative to retry window, decision on whether Raft-backed replication is required.
Split-brain prevention
Goal: Prevent two nodes from simultaneously believing they are the primary/leader.
Stack:
- Lease tokens (#8) — primary holds a time-bounded lease; all writes require a valid lease.
- Fencing tokens (#8) — monotonically increasing integer issued at each lease grant; storage layer rejects writes with a token lower than the maximum seen.
- Paxos (#3) or Raft (#4) termination — after a partition heals, run a full election round before granting a new lease; never grant a new lease without quorum acknowledgement.
When to add Quorums (#9): For storage nodes that cannot run Paxos/Raft, enforce W > N/2 so no two disjoint quorums can each accept a write.
Inputs: N (cluster node count), AZ layout (nodes per AZ), lease duration (ms), fencing token current value, election timeout range (ms), network round-trip time estimate (ms), write latency SLO (p99 ms). Rules: Quorum = ⌊N/2⌋+1; a new lease may only be granted after a full election round with quorum acknowledgement; fencing token must be monotonically increasing and stored durably; storage must reject any write carrying a token ≤ max_seen_token; lose any AZ → remaining nodes must still meet quorum for the cluster to accept writes; for non-Raft storage enforce W > N/2. Outputs: Quorum size, recommended AZ node distribution, fencing token increment policy, write p99 latency estimate (network RTT + leader processing), maximum single-AZ failure tolerance, flag indicating whether quorum enforcement alone is sufficient or Paxos/Raft is required.
Worked example: 5-node Raft cluster, single-AZ failure tolerance. Quorum = ⌊5/2⌋+1 = 3. Deploy: AZ-A holds 2 nodes, AZ-B holds 2, AZ-C holds 1. Lose AZ-A → 3 nodes alive → quorum holds, cluster available. Lose AZ-B + AZ-C → 2 nodes alive → below quorum, cluster unavailable (correct: safety preserved). Fencing token increments on each new lease grant; a deposed AZ-A leader resuming after a GC pause sends token=4, storage has seen token=5, write rejected. Write latency budget: 1 RTT leader→client ack waits for fastest 2 followers: p50 = 8 ms, p99 = 25 ms, plus 5 ms leader processing → write p99 ≈ 30 ms. Shrinking to a 3-node cluster (quorum = 2) drops write p99 to ~13 ms but loses tolerance for any two-node AZ failure — exactly the availability/latency trade-off PACELC quantifies.
Gossip-based state dissemination
Goal: Propagate cluster membership or soft state to all nodes with eventual convergence and no single point of failure.
Stack:
- Gossip / epidemic broadcast (#11) — each node periodically selects k random peers and exchanges state digests; convergence is O(log N) rounds.
- CRDTs (#6) — model disseminated state as a CRDT (e.g. OR-Set for membership) so merge at any node is safe and idempotent regardless of message order.
- Vector Clocks (#5) — attach a vector clock to gossip payloads to detect and discard stale updates.
Inputs: N (cluster node count), gossip fan-out k (peers per round), state model (membership list, soft metric, counter, set), update frequency (updates/s), acceptable convergence time (ms or rounds), network partition tolerance requirement. Rules: Convergence time ≈ O(log N) gossip rounds; each round selects k peers uniformly at random; state must be modelled as a CRDT (G-Counter, OR-Set, LWW-Register, or
…(truncated)