# DDIA Ch. 9: there is no safe failure-detection timeout ## Concept A healthy node answers heartbeats fast almost always — median round-trip time **50 ms** — but load spikes, GC pauses, and network queueing give its RTT a **heavy tail**: an occasional response takes hundreds of milliseconds, and the extreme tail runs into *seconds*. You pick a failure-detection timeout and reason "median is 50 ms, so **300 ms** — six times the median — surely never fires on a live node." It fires on **3.66%** of them. This exercise sweeps the timeout `T` and measures two curves that *cannot both be small*: the **false-positive rate** `P(healthy RTT > T)` — a live node wrongly declared dead — and the **detection delay** `≈ T` you must wait before declaring a genuinely dead node dead. Driving one toward zero drives the other toward infinity. You predict "~0% false positives at my safe 300 ms" and measure **one healthy node in 27** wrongly buried. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 9 — *The Trouble with Distributed Systems*, §"Timeouts and Unbounded Delays" (and §"Network congestion and queueing"). The book's claim, tightly paraphrased: a **long** timeout means a long wait before a dead node is declared dead; a **short** timeout detects faults faster but risks wrongly declaring a live node dead when it has only suffered a temporary slowdown. Because asynchronous networks have **unbounded** delay — no guaranteed maximum transit time, and hosts with no bounded response time — there is no "correct" value for the timeout; it has to be chosen experimentally, trading one failure mode off against the other. Here you produce the two curves and measure the irreducible false-positive floor at the "safe" timeout. ## Prerequisites The whole result is carried by one fact — the delay distribution has a **heavy tail with no upper bound**. Each line notes where it shows up below. 1. **Heavy-tailed / lognormal distributions** — right-skewed, median ≪ mean, a long right tail that never hits a hard ceiling. It shows up as the RTT model `log(RTT) ~ Normal(μ, σ)` whose p99.9 is 22× its median. **This one carries the result:** a thin-tailed (bounded) distribution would let a finite timeout reach zero false positives; the fat tail is exactly what forbids it. 2. **The false-positive vs detection-delay trade-off** — a timeout is a classifier ("slow ⇒ dead") with two error modes that trade off. It shows up as the two columns of the Step 3 sweep moving in opposite directions. 3. **Why async networks give no upper bound on delay** — a packet can be queued, retransmitted, or reordered for an unbounded time; there is no `T_max`. It shows up as the false-positive rate reaching exactly 0 only at `T = ∞`. 4. **Queueing** — the physical mechanism behind the tail: when a switch port, NIC, or CPU run-queue is momentarily saturated, requests wait in line, and waits compound. It shows up as the "occasional multi-second spike" in a node that is otherwise 50 ms. 5. **The lognormal CDF / the standard-normal `Φ`** — `P(RTT > T)` is computed *exactly* as `1 − Φ((ln T − μ)/σ)`, no sampling needed. It shows up as `statistics.NormalDist().cdf`, which makes every number reproduce to the digit. ### Where to learn the prerequisites - **Heavy tails & the lognormal (#1, #5):** the Wikipedia "Log-normal distribution" article is enough — you only need "right-skewed, parameterized by the μ/σ of an underlying normal, and its quantiles are `exp(μ + σ·z)`." For *why* tails matter operationally, **Gil Tene, "How NOT to Measure Latency"** (talk on YouTube/InfoQ). - **Unbounded delay & timeouts (#2, #3):** DDIA §"Timeouts and Unbounded Delays" and §"Network congestion and queueing" — the source paragraphs. For the failure detector framing, Chandra & Toueg, "Unreliable Failure Detectors for Reliable Distributed Systems" (1996), on completeness vs accuracy. - **Queueing (#4):** any intro to queueing theory (the M/M/1 waiting-time curve); the intuition that matters is "utilization near 1 makes wait blow up." If only one is new, make it **#1** — the heavy, unbounded tail is the entire reason there is no safe timeout. ## Environment Every number below was captured on this exact environment. The analytic values are exact; the Monte Carlo is seeded, so it reproduces to the digit: - macOS 26.5.2 (Darwin 25.5.0), arm64 - Python 3.15.0a8, standard library only — `math`, `random`, `statistics` - RTT distribution fixed: `log(RTT) ~ Normal(μ = ln 50, σ = 1.0)`, median 50 ms - `P(RTT > T)` evaluated analytically via `statistics.NormalDist`; the cross-check draws `1,000,000` samples with `random.Random(42)` ## Mental model Model one healthy node's round-trip time as a right-skewed **lognormal**, tuned so the median is **50 ms** and the tail is fat (`σ = 1.0`): a p99 of ~500 ms and an extreme tail into the seconds. The node is *never actually dead* — every RTT is a real, eventual response. A failure detector waits `T` for a heartbeat and, if none arrives, declares the node dead. That is a **bet**: "a response this slow means the node is gone." Two quantities move as `T` grows, in opposite directions: - **False-positive rate** `P(healthy RTT > T)` — the fraction of a *live* node's heartbeats that overshoot `T` and get it wrongly buried. This is just the tail mass of the distribution above `T`, computed exactly as `1 − Φ((ln T − μ)/σ)`. - **Detection delay** `≈ T` — for a node that *is* genuinely dead, you learn nothing until the timeout elapses, so you wait about `T` before you may declare it dead. Because the tail is heavy and **unbounded**, there is no `T` that makes the first zero at any finite value of the second. A timeout is a bet that a heavy tail makes wrong a fixed, non-zero fraction of the time — and the only way to lower that fraction is to wait longer. The whole exercise is one script, `code/no_safe_timeout.py`. ## Setup ``` cd study/ddia/ch09/code python3 no_safe_timeout.py ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — the healthy node's RTT (calibration) **Predict.** RTT is lognormal with median 50 ms and `σ = 1.0`. Before looking: roughly what is its p99? Its p99.9? (These set how far the tail reaches above the median.) **Do.** Run the script; read the first block. **Observe.** ``` RTT ~ lognormal(mu=3.912, sigma=1.0) => median = 50 ms p50 = 50.0 ms p90 = 180.1 ms p99 = 512.0 ms p99.9 = 1099.1 ms p99.99 = 2061.2 ms ``` The median is 50 ms, but the p99 is already **512 ms** (10× the median) and the p99.9 is **1099 ms** — over a full second. The node is healthy; it just occasionally answers slowly. Fix in your head that a *live* node routinely emits RTTs in the hundreds of ms. ### Step 2 — the "obviously safe" 6× timeout (the surprise) You choose `T = 300 ms`: six times the median, which *feels* like generous headroom over a 50 ms node. **Predict.** What fraction of a *healthy* node's heartbeats exceed 300 ms and get it wrongly declared dead? Write a number down before revealing. (Most people say "≈ 0", or hedge to "well under 1%".) **Observe.** ``` Timeout T = 300 ms (6x the 50 ms median headroom) FALSE-POSITIVE RATE P(healthy RTT > 300 ms) = 0.0366 = 3.66% i.e. 1 healthy heartbeat in 27 is wrongly declared DEAD. ``` **3.66% — one healthy node in 27, not ~0.** Six times the median sounds like a wall of headroom, but the lognormal tail still has 3.66% of its mass above 300 ms. Every heartbeat that lands there is a live node mistaken for a corpse — and nothing errored to warn you. ### Step 3 — the sweep: false positives vs detection delay **Predict.** Now sweep `T`. Is there a timeout in the list where *both* the false-positive rate and the detection delay are small — say FP under 0.1% *and* delay under a few hundred ms? **Observe.** ``` T (ms) false-positive rate detection delay (dead) ------ ------------------- -------------------- 100 24.4109% 100 ms 200 8.2829% 200 ms 300 3.6586% 300 ms <- 6x median 500 1.0651% 500 ms 1000 0.1369% 1000 ms 2000 0.0113% 2000 ms 5000 0.0002% 5000 ms ``` **No such row exists.** The two columns move in opposite directions: the only way to push the false-positive rate down a decimal place is to add hundreds or thousands of ms to the wait before you can detect a genuinely dead node. FP under 0.1% costs a **≥ 1-second** detection delay. This is the Pareto trade-off the book asserts — you can buy either fast detection or few false positives, never both. ### Step 4 — chasing zero Look at what timeout each false-positive target actually costs (same run). **Predict.** How large must `T` be to reach a truly negligible false-positive rate — and at what value of `T` does it hit *exactly* zero? **Observe.** ``` to reach FP = 1.000% need T = 512 ms ( 10x median, wait 0.51 s per dead node) to reach FP = 0.100% need T = 1099 ms ( 22x median, wait 1.10 s per dead node) to reach FP = 0.010% need T = 2061 ms ( 41x median, wait 2.06 s per dead node) ``` Each factor-of-ten cut in false positives costs roughly another second of detection delay — and it never reaches exactly zero at any finite `T`. Those timeouts are just the RTT's own p99, p99.9, p99.99: to get the false-positive rate to `x` you must set `T` to the `(1−x)` quantile of the tail, which climbs without bound. ### Monte Carlo cross-check The false-positive numbers above are exact (from the lognormal CDF). A seeded million-sample draw confirms them and shows the tail is real: ``` empirical P(RTT > 300 ms) = 3.6622% (analytic 3.6586%) empirical p50 = 50.0 ms (analytic 50.0 ms) empirical p99 = 509.8 ms (analytic 512.0 ms) empirical max = 11407.1 ms over 1,000,000 draws ``` The empirical 3.6622% lands on the analytic 3.6586%, and the largest of a million healthy RTTs is **11.4 seconds** — a node that is perfectly alive and would blow through *any* of the timeouts in the sweep. ## What you should see - RTT p50 = **50 ms**, p99 = **512 ms**, p99.9 = **1099 ms** — a fat, unbounded tail on a healthy node. - At the "safe" 6× timeout (**300 ms**) the false-positive rate is **3.66%** — 1 healthy node in 27 wrongly declared dead, *not* ~0. - Across the sweep, false-positive rate and detection delay trade off strictly: **24.4% → 0.0002%** as `T` goes **100 ms → 5000 ms**, with detection delay rising in lockstep. No row has both small. - The false-positive rate reaches exactly 0 only as `T → ∞`. ## Why A timeout is a classifier with one input — "did a heartbeat arrive within `T`?" — and it inherits the two error modes of every classifier. Declaring too eagerly (`T` small) buries live nodes; declaring too patiently (`T` large) leaves dead nodes undetected for a long time. What makes the trade-off *irreducible* here is the **shape of the delay distribution**. The false-positive rate at timeout `T` is by definition the tail mass `P(RTT > T)` — the fraction of a healthy node's own responses that arrive later than `T`. For a lognormal that is `1 − Φ((ln T − μ)/σ)`, and with `μ = ln 50, σ = 1.0` the 300 ms point is `1 − Φ((ln 300 − ln 50)/1.0) = 1 − Φ(ln 6) = 1 − Φ(1.792) = 0.0366`. The "6× median" intuition fails because "6× the median" is only `Φ(ln 6) = 96.3%` of the way into a tail this fat — the top 3.7% still lies beyond it. Now the key move: to make that tail mass zero you would need a `T` beyond the distribution's maximum, and a lognormal — like a real asynchronous network — has **no maximum**. There is always more tail. So `P(RTT > T) > 0` for every finite `T`, and it shrinks to 0 only in the limit `T → ∞`, i.e. a node you never declare dead (infinite detection delay). Equivalently: to hit false-positive rate `x` you must set `T` to the `(1−x)` quantile of the RTT, which is `exp(μ + σ·z_{1−x})` and grows without bound as `x → 0`. That is precisely why the book says there is no correct timeout value — with an unbounded delay distribution, no single `T` simultaneously gives `P(healthy > T) = 0` and a finite wait. The two goals are the same knob turned opposite ways. **The boundary — a *bounded-delay* network does have a safe timeout.** The result hangs entirely on the tail being unbounded. In a **synchronous, real-time** system — a network with a guaranteed maximum transit time and hosts with bounded, pre-emptible response times — the RTT distribution has a hard ceiling `D_max`. There, `T = D_max` gives a false-positive rate of *exactly* zero (nothing healthy ever exceeds it) *and* a finite detection delay of `D_max`. This is why avionics buses, industrial control networks, and hardware watchdog timers *can* set a provably safe timeout: they pay (in cost, in utilization headroom, in special hardware) to bound the tail. Commodity datacenters and the public internet make the opposite trade — cheap, statistically multiplexed, best-effort — and buy an *unbounded* tail with it. Remove the ceiling and the safe timeout vanishes. ### Go deeper 1. **Thin the tail.** Halve `SIGMA` to 0.5 (same 50 ms median) and re-run. The false-positive rate at 300 ms collapses toward zero — evidence that the result is a property of the *tail*, not the median. A tighter node genuinely does have a safer timeout; it just still isn't *exactly* zero at any finite `T`. 2. **Phi-accrual failure detectors.** Instead of a hard yes/no at one `T`, output a continuous *suspicion level* `φ = −log₁₀ P(RTT > elapsed)` — the very tail probability computed here — and let each consumer pick its own threshold. Cassandra and Akka use this. Add a function that prints `φ` as elapsed time grows and watch suspicion accrue smoothly instead of snapping. 3. **Adaptive timeouts.** Have `T` track the node's *recent* RTTs (e.g. the running p99 of the last 100 samples) instead of a fixed constant, so a node under transient load is judged against its own current tail. Measure how the false-positive rate changes when the load level shifts mid-stream.