Note: Company names, engineers, incidents, numbers, and scaling scenarios in this article are hypothetical — even when they resemble real ones. See the full disclaimer.

Phi accrual failure detector

It is 14:08 on a Tuesday and Asha, a platform engineer at PaySetu, is staring at a flame graph nobody asked her to produce. The cluster is fine. The detector says so. The detector has been saying so for the last 47 minutes, even as the application's payment-authorisation p99 climbed from 80 ms to 2.4 s and then settled, mysteriously, at 1.8 s. Half the on-call rotation is convinced node-7 is "kind of dead" — its acks are arriving 3.8 s late on average, but never late enough to trip the 5-second timeout. The other half says the dashboard is green so node-7 is healthy by definition. Asha is about to discover that this argument is the wrong one — that "alive" and "dead" are not the only states a node can be in, and that the right question is not "is node-7 dead?" but "how suspicious am I right now?"

The thing the timeout cannot do

The four-line detector from the previous chapter makes one decision and makes it once: a peer is alive if now - last_seen ≤ T, dead otherwise. Phi accrual makes a different choice: it never decides. It exposes a number φ (the Greek letter phi, written phi in code), and the number grows the longer it has been since the last heartbeat. The application reads φ and decides what to do at what threshold.

The point of the Hayashibara, Défago, Yared and Katayama paper — "The φ Accrual Failure Detector", SRDS 2004 — was not the formula. The formula is fifteen lines of Python. The point was the separation of concerns. The detector knows the network's recent jitter; the application knows whether a false positive costs ₹40 lakh of failed payments or ₹40 of refunded fares. Two different applications reading the same heartbeat stream will want two different thresholds, and the right design is to compute φ once and let each application threshold it independently. Why a single fixed timeout T cannot do this: a timeout is the application's threshold baked into the detector. Once you bake it in, you cannot give a second application a different operating point on the ROC curve without running a second detector — second heartbeat thread, second last_seen table, second sliding window. Phi accrual factors out the part that depends only on the network, leaves the part that depends on the application, and lets one signal serve many policies.

The shape of φ against time is the key picture. While heartbeats are arriving at their expected cadence, φ ≈ 0. The instant after a heartbeat arrives, φ resets toward 0. As silence stretches past the mean inter-arrival time, φ climbs — but how fast it climbs depends on the variance of the recent inter-arrival distribution. On a quiet LAN with σ=2 ms, three seconds of silence after a 100 ms heartbeat is catastrophic; φ shoots above 12. On a congested AZ-trunk with σ=400 ms, the same three seconds of silence is unremarkable; φ rises only to 1.8. Same elapsed time, same last_seen gap, very different verdicts — because the detector has learned what "normal silence" looks like on this specific link.

Deriving phi from the inter-arrival distribution

Here is the formula, derived. Keep a sliding window W of the last k inter-arrival times — the gaps between consecutive heartbeats from a peer. Compute the sample mean μ and sample standard deviation σ of this window. Now, at any wall-clock instant t, define the elapsed silence as Δ = t - last_seen. Treat the inter-arrival distribution as approximately normal with parameters (μ, σ²) — this is the central modelling assumption, and it is wrong in the tail but useful in the body. The probability that a heartbeat would arrive at or after time Δ is then:

P_later(Δ) = 1 - F(Δ; μ, σ)

where F is the cumulative distribution function of the normal. Phi is the negative base-10 logarithm of this probability:

φ(Δ) = -log10( P_later(Δ) )

So φ = 1 means "there is a 10% chance a real heartbeat is still in flight"; φ = 3 means "a 0.1% chance"; φ = 8 means "a 10⁻⁸ chance" — about one in a hundred million. Why the log10: it converts a probability that hugs zero in the tail into a number that scales linearly. P_later = 10⁻⁵ and P_later = 10⁻⁶ look identical on a probability axis but differ by 1.0 on the φ axis — the application can write if phi > 5: act and reason in orders of magnitude. The unit of φ is "decibans of suspicion", and that framing — drawn from Turing's wartime cryptanalysis at Bletchley — is what makes the threshold values φ=3 and φ=8 feel intuitive once you have lived with them for a quarter.

The Hayashibara paper proves a subtle property: under the assumption that inter-arrival times follow a known distribution, φ has a frequentist interpretation — at threshold φ = T, the long-run rate of false positives is 10⁻ᵀ per evaluation. So φ > 8 corresponds to a false-positive probability of 10⁻⁸, if the inter-arrival distribution is actually normal and stationary. Both assumptions are wrong in production — distributions are heavy-tailed (TCP retransmits, GC pauses) and non-stationary (load varies by hour). But the relative ordering — φ = 8 is much more cautious than φ = 3 — survives even when the absolute calibration fails. Cassandra ships with phi_convict_threshold = 8 because that is where empirical false positives drop into the "operationally acceptable" range on AWS networks. Akka ships with a default of 8 too, with a min-std-deviation = 100 ms floor to avoid pathological overconfidence on very-quiet links.

The distribution choice matters. Hayashibara's original paper used a normal distribution. Cassandra uses an exponential distribution, which fits better when inter-arrival jitter is dominated by network queueing. The Cassandra choice means the formula simplifies — for an exponential Exp(λ) with λ = 1/μ, P_later(Δ) = exp(-λΔ) = exp(-Δ/μ), so φ = Δ / (μ × ln(10)). The exponential variant is faster to compute (no error-function call) and just as well-calibrated for the operating regime where it is used. For LAN-internal cluster traffic where most jitter is bufferbloat-shaped, the exponential variant is the right default; for WAN traffic where jitter is more bell-shaped, the normal variant tracks more accurately.

A note on the sliding-window mechanism. The window is updated only on heartbeat arrival — no entries are added during silence, no entries are removed by ageing. This is correct: φ is computed from how the network has been behaving when packets do arrive, and silence is the fact under measurement, not the input. A bug seen in early implementations was to age out entries during long silences, which artificially inflated the variance (because the window contained fewer, more spread-out samples), which suppressed φ exactly when the cluster needed it most. The discipline: window is a record of arrivals, period.

Building it from scratch — the runnable version

This is a complete phi-accrual detector in Python. It maintains a sliding window of inter-arrival times, computes phi on demand, and exposes both the φ value and the underlying statistics for debugging.

import math, time, statistics, threading
from collections import deque

class PhiAccrualDetector:
    def __init__(self, window_size=1000, min_std_ms=100, threshold=8.0):
        self.intervals = deque(maxlen=window_size)
        self.last_arrival = None
        self.min_std_ms = min_std_ms
        self.threshold = threshold
        self.lock = threading.Lock()

    def heartbeat(self, now_ms=None):
        now_ms = now_ms if now_ms is not None else time.time() * 1000
        with self.lock:
            if self.last_arrival is not None:
                self.intervals.append(now_ms - self.last_arrival)
            self.last_arrival = now_ms

    def phi(self, now_ms=None):
        now_ms = now_ms if now_ms is not None else time.time() * 1000
        with self.lock:
            if self.last_arrival is None or len(self.intervals) < 2:
                return 0.0
            mu = statistics.fmean(self.intervals)
            sigma = max(statistics.pstdev(self.intervals), self.min_std_ms)
            delta = now_ms - self.last_arrival
            # exponential variant — Cassandra's choice
            p_later = math.exp(-delta / mu) if mu > 0 else 0
            # floor at 1e-12 to avoid log(0)
            return -math.log10(max(p_later, 1e-12))

    def is_available(self):
        return self.phi() < self.threshold

# simulate 60 seconds of heartbeats at 100 ms cadence with 20 ms jitter,
# then a 4 second silence, then resumption
import random
det = PhiAccrualDetector(threshold=8.0)
t = 0.0
random.seed(42)
for i in range(600):
    t += 100 + random.gauss(0, 20)
    det.heartbeat(now_ms=t)

# now silence for 4 seconds, sample phi every 250 ms
print(f"baseline mu={statistics.fmean(det.intervals):.1f} ms "
      f"sigma={statistics.pstdev(det.intervals):.1f} ms")
for step in range(17):
    probe = t + step * 250
    print(f"  silence={step*250:>4} ms  phi={det.phi(now_ms=probe):>5.2f}  "
          f"available={det.phi(now_ms=probe) < 8.0}")

Running this script produces:

baseline mu=99.6 ms sigma=20.4 ms
  silence=   0 ms  phi= 0.00  available=True
  silence= 250 ms  phi= 1.09  available=True
  silence= 500 ms  phi= 2.18  available=True
  silence= 750 ms  phi= 3.27  available=True
  silence=1000 ms  phi= 4.36  available=True
  silence=1250 ms  phi= 5.45  available=True
  silence=1500 ms  phi= 6.54  available=True
  silence=1750 ms  phi= 7.63  available=True
  silence=2000 ms  phi= 8.72  available=False
  silence=2250 ms  phi= 9.81  available=False
  ...

The behaviour: at threshold φ=8, the detector declares the peer unavailable after roughly 1.85 seconds of silence — about 18× the mean inter-arrival time, which is the "right" answer for a μ=100 ms cadence under tight jitter. The line sigma = max(statistics.pstdev(self.intervals), self.min_std_ms) enforces a floor on the variance estimate; without it, a peer that has been steady for a long time has σ → 0 and any silence whatsoever shoots φ to infinity, producing absurd false positives on the first delayed packet. The line p_later = math.exp(-delta / mu) is the exponential-variant body — for the normal variant, swap in 0.5 * math.erfc((delta - mu) / (sigma * math.sqrt(2))). The defaultdict-style window grows for free — a real production detector adds a periodic sanity-check (variance gone negative, last_arrival in the future, NaN propagation) because once these statistics accrue garbage, the detector silently broadcasts garbage too. The threshold 8.0 is Cassandra's default — Akka's acceptable-heartbeat-pause (3 s with 1 s heartbeat at threshold 8) corresponds to roughly the same operating point.

Where phi accrual lives in production

Three real systems give phi accrual prime billing. Cassandra's o.a.c.gms.FailureDetector is the canonical reference implementation — phi_convict_threshold defaults to 8, exposed as a cassandra.yaml knob. Operators tune it down to 5 on noisy networks (more aggressive, more false positives but faster real-failure detection) and up to 12 on clean LANs (fewer false positives, slower detection). Akka's akka.remote.classic.transport-failure-detector and akka.cluster.failure-detector use phi accrual with a minimum-std-deviation floor — the floor is what stops the detector from going pathological when σ collapses. Hazelcast's hazelcast.heartbeat.phi.failure.detector.threshold defaults to 10, slightly higher than Cassandra, because Hazelcast clusters trend smaller and the cost of a false positive (a cache miss) is lower than Cassandra's (a coordinator-rebalance).

CricStream had a phi-tuning incident worth retelling. Their event-fanout cluster — 47 nodes coordinating live-score fan-out across two AZs — ran with the Akka default threshold=8. During an IPL playoff match, traffic crossed 18M concurrent viewers and the inter-AZ trunk's σ rose from 4 ms (steady state) to 28 ms (under load). The detector adapted correctly — it raised its tolerance in proportion to the variance — and survived the load test. Three weeks later, during the final, the trunk's σ momentarily hit 600 ms because of a load-balancer reconfiguration. The detector adapted too well: σ saturated to a value where 2.4 seconds of silence still gave φ≈3, and the cluster spent 12 minutes treating a genuinely-dead node as merely-slow before a human intervened. The fix the team converged on, after the post-mortem, was an Akka-style cap: max-std-deviation = 200 ms. The detector is allowed to learn up to that bound, and beyond it, the operator's prior — "no real network has σ > 200 ms in steady state" — wins. The cap cost the cluster ~30 ms of detection latency under genuine network stress and saved it from the 12-minute pathology. The trade was operationally obvious only in hindsight; the team had to ship the cap, see it work, and only then articulate why. Why a max-std cap is the operator's prior, not a hack: the inter-arrival distribution the detector sees is not the inter-arrival distribution that exists. It is the distribution of the events the detector hears about. If a transient event makes σ explode, the detector can either (a) believe its eyes and disable itself, or (b) believe the operator's hand-coded prior that says "in normal operation σ never exceeds X ms". Production overwhelmingly picks (b), because a detector that disables itself during a network event is exactly the wrong behaviour — that is when you most need it.

Common confusions

• "Phi accrual is just a fancy timeout." The fixed timeout T is a single point on the ROC curve baked into the detector. Phi accrual exposes the entire curve as a number φ and lets the application choose any point on it, and lets two applications choose different points on the same input stream. The "fancy" part is the separation of concerns, not the formula.
• "You should always use threshold φ=8." Eight is Cassandra's default, calibrated for AWS network jitter circa 2010. It is a starting point, not an axiom. KapitalKite runs threshold 5 on its market-data path (false positives are cheap — a re-route — and false negatives are expensive — stale prices). PaySetu runs threshold 11 on its long-tail UPI authoriser path (false positives trigger expensive reshards). One number does not fit all paths in one cluster, let alone all clusters in an industry.
• "Phi accrual handles asymmetric partitions." It does not. If A is sending heartbeats to B and B receives them, B's φ for A stays near zero — even if B's heartbeats to A are being silently dropped. Phi only sees the receive-side signal; an asymmetric partition is invisible to it. SWIM's indirect probing covers this; phi alone does not. (The animated SVG above shows this gap explicitly.)
• "More heartbeats per second mean better phi." Up to a point. Doubling the heartbeat rate halves μ and roughly halves the time it takes for φ to cross any given threshold — if the variance shrinks proportionally. In practice the variance is dominated by network conditions, not heartbeat cadence, so doubling the rate doubles the network cost for less than 2× detection-speed gain.
• "Phi accrual replaces SWIM." They solve different problems. Phi is the signal — how suspicious am I? SWIM is the protocol — how do I propagate that suspicion to the rest of the cluster, and how do I probe peers indirectly when my own signal is degenerate? Production systems layer them: SWIM-style indirect probing feeds heartbeat arrival times into a phi-accrual computation, and gossip propagates suspicion verdicts. See SWIM protocol.
• "The min-std-deviation floor is a workaround." It is the operator's prior, not a hack. Without it, a perfectly steady link has σ → 0 and one delayed packet sends φ to infinity. The floor encodes the operator's belief that "no real network is exactly steady — there is always some irreducible jitter, and anything claiming less is a measurement artefact". Every production phi-accrual detector ships with this floor and it is correctly considered part of the algorithm, not a patch. The same logic explains why production detectors also ship a startup-grace window: a brand-new node hasn't accumulated enough inter-arrival samples to estimate σ at all, so φ is biased high in its first minute. Without the grace window, new nodes are routinely declared dead in their first minute — a self-inflicted false positive that nothing about the network caused.

Going deeper

The Hayashibara paper and where its assumptions break

The 2004 SRDS paper proves that under a known stationary inter-arrival distribution, the detector at threshold φ = T produces false positives at rate 10⁻ᵀ per evaluation. Two assumptions are violated in practice. First, stationarity: real networks have non-stationary jitter — daytime σ is different from nighttime σ, weekend is different from weekday, and a load-balancer reconfiguration in another AZ changes σ instantly. The sliding-window estimate of μ and σ chases the true distribution with a delay of W/2 inter-arrival times; for W=1000 and μ=100 ms that is 50 seconds, which is forever in incident time. Second, known distribution shape: real jitter is heavy-tailed, and the normal/exponential approximation is wrong specifically in the tail where the threshold operates. The result is that the calibration φ=8 → 10⁻⁸ false-positive rate is wrong by orders of magnitude in the wrong direction during incidents — exactly when you most need calibration. Operators who treat φ=8 as an empirical threshold ("this is what works on our network") rather than a probability claim ("this gives one false positive in ten million") avoid the worst of this trap.

Why Cassandra picked the exponential variant and Akka picked normal

Cassandra's failure detector models inter-arrival as exponential — P_later(Δ) = exp(-Δ/μ). The rationale, in the Cassandra source comments, is that LAN heartbeats look more like Poisson arrivals (queueing-dominated) than Gaussian arrivals (sum-of-many-small-effects). The exponential variant has a single parameter (no σ) and is computationally cheap.

Akka's failure detector models inter-arrival as normal with explicit σ tracking. The rationale is that Akka clusters often run on JVMs with GC pauses, and GC pauses produce a bimodal distribution — most arrivals are tight, occasional arrivals are during-GC and far-tailed. The variance estimate captures this bimodality in a way that the exponential's single parameter cannot. Both are right for their context, and a port of one to the other's workload would visibly underperform.

What goes wrong when the heartbeat sender pauses

A subtle case: the heartbeat sender's GC pauses — not the application's. If node A sends heartbeats every 100 ms, and A's heartbeat-sending thread (separate from the application) experiences a 2-second GC pause, then from B's perspective B sees 2 seconds of silence even though A is healthy. Phi correctly identifies this as suspicious. The mistake is treating phi's verdict as the application's verdict — the right architecture splits liveness ("can A respond to RPCs?") from membership ("is A still in the cluster?"), and phi feeds membership while a separate, application-aware probe feeds liveness. KapitalKite's resolution rule from the previous chapter (mesh-view authoritative for traffic, Raft-view authoritative for state) is the practical version of this split.

The relationship between phi and the leaky-bucket smoothed timeout

A simpler smoothing scheme — the Jacobson/Karels TCP RTT estimator — also adapts a timeout based on observed jitter: RTO = SRTT + 4 × RTTVAR, with both SRTT and RTTVAR updated by exponential moving averages on every observed RTT. This is in TCP since RFC 793.

Phi accrual is a more flexible cousin: it exposes a number rather than baking the threshold (+ 4 × RTTVAR) into the formula. For TCP's purpose — "should I retransmit this packet?" — the baked-in formula is fine because the application is fixed. For a cluster failure detector serving multiple downstream consumers — leader election, membership, lease renewal — phi's separation of concerns is what makes it the right tool.

Tuning the sliding window size

The window size W controls how quickly the detector adapts to changing network conditions. Small W (say 50): the estimator chases the current jitter aggressively, so a brief congestion event raises σ within seconds and the detector stops false-positiving on the same congestion's tail. Large W (say 5000): the estimator is slow to react, so a gradual deterioration — say, a slowly-failing NIC that adds 20 ms to every packet — never raises σ enough to compensate, and false positives accumulate. MealRush's order-fan-out cluster ran with W=200 and saw 14 false positives during a 12-minute degradation event; raising to W=1000 cut that to 2. The reverse-direction tradeoff: at W=5000 the detector is too sluggish to react to the removal of a congestion event — the cluster suffers latency tax for the entire window's worth of inter-arrivals after the network recovers. The empirical sweet spot for most production clusters lands at W between 500 and 2000, with the upper bound when the heartbeat cadence is fast (≤100 ms) and the lower bound when the cadence is slow (≥1 s).

Reproduce this on your laptop:

python3 -m venv .venv && source .venv/bin/activate
# statistics is in stdlib for Python 3.11+; no external deps needed
python3 phi_accrual.py  # the script above, saved to phi_accrual.py
# Try changing window_size, min_std_ms, threshold; observe the silence-to-eviction time.

Where this leads next

The next chapter, SWIM protocol, addresses what phi cannot — asymmetric partitions and the O(N²) heartbeat traffic of all-pairs detection — by using indirect probing and gossip. The chapter after that, gossip-based membership (Serf), is the production walkthrough.

Where phi accrual fits in the broader detector arc: phi is the suspicion signal. SWIM is the probe protocol. Lifeguard is the suspicion-propagation policy. Rapid is the consensus-on-membership layer that prevents false-positive cascades. Each layer addresses a failure mode the lower layer cannot, and a production failure detector at scale is all four layered together. Cassandra's source is the cleanest reading-order: start at FailureDetector.java, work outward to Gossiper.java, then EndpointState.java. The 1500 lines that result are the Cassandra-shaped answer to "what is the right failure detector?", and they sit on top of the 30 lines of phi accrual you wrote above.

The takeaway worth carrying forward: every "alive vs dead" question in distributed systems is really a "how confident am I right now" question. The systems that get failure detection right — Cassandra, Akka, Hazelcast, the production-tuned variants at PaySetu and CricStream — share that framing. The systems that get it wrong almost always share the opposite framing — a single timeout, baked into the detector, applied uniformly across all consumers, recalibrated only after the next outage.

References

• Hayashibara, N., Défago, X., Yared, R., Katayama, T. — "The φ Accrual Failure Detector" (SRDS 2004) — the original paper. Read §3 (the formal derivation) and §5 (the experimental calibration on a 10-node testbed).
• Apache Cassandra source — o.a.c.gms.FailureDetector.java — the canonical production implementation. Read the comments around interArrivalTime for the variance-estimation discipline and the phi_convict_threshold rationale.
• Akka documentation — akka.cluster.failure-detector configuration reference — phi accrual with min-std-deviation and acceptable-heartbeat-pause parameters explained.
• Jacobson, V. — "Congestion Avoidance and Control" (SIGCOMM 1988) — the SRTT/RTTVAR adaptive-timeout scheme that phi accrual generalises.
• Chandra, T., Toueg, S. — "Unreliable Failure Detectors for Reliable Distributed Systems" (JACM 1996) — classifies detectors by completeness and accuracy; phi accrual sits in the ♦P (eventually perfect) class.
• Heartbeats: the naive approach — the previous chapter; the four-line detector phi accrual replaces.
• Wall: failure detection is its own problem — the framing chapter that explains why no detector is perfect.
• Das, A., Gupta, I., Motivala, A. — "SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol" (DSN 2002) — the next chapter's foundation; phi as a signal, SWIM as the protocol that propagates it.