Phi Accrual Detectors: Turning Inter-Arrival Samples into a Continuous Suspicion Level

A fixed timeout answers a binary question with a hard number, and the number is a bet about a network that has no obligation to honour it. The accrual approach replaces the bet with a measurement: it keeps the recent history of gaps between heartbeats, asks how unusual the current gap is against that history, and reports the answer as a continuous value rather than a yes or no. The system consuming the value decides what value is worth acting on.

The quantity the detector computes

Let t_last be the time of the most recent heartbeat and t_now the current time. The current gap is T = t_now - t_last. The detector holds a sample of the previous inter-arrival gaps and uses it to model the distribution of gaps. Under that model it computes the probability that a live process would have shown a gap of at least T. Call that P_later(T).

The suspicion level is defined as the negative base-10 logarithm of that probability:

phi(T) = -log10(P_later(T))

The definition is where the design’s portability comes from. A probability of 10^-1 gives phi = 1; 10^-8 gives phi = 8; 10^-16 gives phi = 16. The scale is exponential in the probability, so a threshold on phi corresponds to a fixed order of magnitude of confidence, and the same threshold means roughly the same thing on a fast network and a slow one. A threshold of 8 asserts that a gap this long would occur by chance about once in a hundred million heartbeat gaps. That assertion is about the shape of the distribution, not about any absolute duration.

Fitting a distribution to gaps

The original formulation fits a normal distribution to the gap samples, using their mean and standard deviation, and computes the tail probability from the normal survival function. The choice is pragmatic rather than principled: inter-arrival gaps are not normal, because they are bounded below by zero and skewed, but the normal fit is cheap and the resulting phi is monotone in T, which is all the threshold comparison requires.

The mechanics of maintaining the sample matter more than the choice of family. The detector keeps a bounded window of recent gaps, and it must cope with three regimes.

While fewer than a few samples exist, the mean and deviation are unreliable and the detector must use a floor on the deviation. A deviation of zero, which happens when the first two samples are identical, would make every subsequent gap infinitely improbable and produce a suspicion on the first late beat. The usual fix is a minimum standard deviation, so early decisions are made against a conservative spread rather than an over-confident one.

When the window is full, adding a sample requires evicting one. A ring buffer of the last n gaps does this in constant time, and a window in the range of a few hundred to a couple of thousand samples is typical. The window length sets the adaptation rate: a short window tracks a changing network quickly but makes phi noisy, because the mean and deviation themselves fluctuate with each eviction. A long window is stable but slow to notice that the network has genuinely become slower, during which it reports high suspicion for a healthy peer.

When the peer restarts, the old samples describe a process that no longer exists. The detector must reset its window on a restart, which requires knowing that a restart happened, which is exactly what the detector is supposed to be reporting. The resolution is that the peer’s incarnation or session identifier changes on restart and the detector keys its sample window on that identifier, so a new incarnation starts with an empty history. This is the same identity problem as in suspicion and incarnation refutation, resolved by the same mechanism for the same reason.

Computing the tail cheaply

The normal survival function has no closed form, so implementations use an approximation. The complementary error function is available in most standard libraries, and P_later is expressed through it:

P_later(T) = 0.5 * erfc((T - mean) / (stddev * sqrt(2)))

A detector that evaluates this on every tick spends a special-function call measured in tens of nanoseconds, which is negligible against a heartbeat period measured in milliseconds. An implementation that wants to avoid the special function can precompute a table over the range of (T - mean)/stddev that matters, or can note that phi is only needed for comparison against a threshold and invert the comparison: the threshold phi_0 corresponds to a fixed number of standard deviations above the mean, so the check reduces to T > mean + z(stddev) for a z derived once from phi_0. That reduction is exact under the normal assumption and makes the hot path an integer comparison, at the cost of losing the actual phi value that some consumers want for load balancing or for reporting.

The numerical failure to guard against is underflow. For a gap far out in the tail, P_later is smaller than the smallest representable double, and -log10 of zero is infinite. Clamping the probability to the smallest positive value, or clamping phi to a large finite cap, keeps the value comparable and prevents a consumer from receiving an infinity it must special-case.

What a threshold buys, and what it hides

A threshold on phi is a statement of acceptable false-positive rate per gap. That framing is more honest than a timeout in seconds, and it exposes the assumption the accrual method still makes: the samples are representative of the future.

The assumption fails in a specific and common way. A process that pauses for a long time, whether in a garbage collection cycle, a page fault storm, or a hypervisor deschedule, produces a gap drawn from a distribution that the sample window has never seen. The detector, having only seen short gaps, treats the pause as astronomically improbable, and phi crosses any reasonable threshold well before the pause ends. Raising the threshold does not fix this, because the fitted deviation is small and the tail falls off steeply; the pause is not a rare draw from the same distribution, it is a draw from a different one. The correct remedy is at the observer, not the threshold, and is covered in pause-induced false suspicion.

A second limitation is that the value is not comparable across peers. A peer with an erratic history has a wide fitted deviation, so a long gap yields moderate phi; a peer with a very regular history yields high phi for the same gap. That is the intended behaviour, since the question is whether the gap is unusual for this peer, but it means a system cannot rank peers by phi and conclude that the highest value is the most likely failure. It also means a peer whose heartbeat period was recently changed will be judged against a history that no longer applies, until the window turns over.

Layering decisions above the value

Because phi is continuous, the consumer can implement hysteresis. Declaring a peer failed at phi = 8 and clearing the declaration only when a heartbeat arrives is one policy; declaring at 8 and clearing at 4 gives a dead band that prevents flapping when the gap hovers near the threshold. The band costs accuracy in the sense that a peer returning from a long pause stays marked for a while, but it prevents a pathological cycle of declare and retract that costs far more than the delay.

The value also supports graded responses that a binary detector cannot express. A load balancer can stop routing new requests at a moderate phi and only trigger replacement at a high one, which converts a suspicion into a gradual drain. The trade is that the intermediate state must be understood by every component that reads membership, and a component that treats “moderately suspect” as “healthy” reintroduces the stall the detector was trying to prevent. Fixed-threshold detectors have no such state, which is why they remain common despite the arithmetic in heartbeat interval and timeout arithmetic being harder to get right.

The final limitation is structural. A continuous suspicion level is still a per-observer opinion about a path. It is a better-calibrated opinion than a fixed timeout, and it degrades gracefully instead of stepping, but it does not tell the difference between a peer that is gone and a peer that is reachable from elsewhere. That distinction needs evidence from multiple observers, which is the problem addressed in asymmetric partitions and per-observer diagnosis.