Failure Detection

A node failing to reply might be due to a process crash, network partition, long CPU scheduling delays, or the observer itself being paused. Failure detection first describes what evidence the observer can obtain, and only then decides when to switch services.

In an asynchronous model where message delays have no upper bound, silence for a finite time does not prove that the other party has stopped. This does not mean systems cannot be built; rather, it requires separating "suspicion," "taking action," and "guaranteeing safety."

Heartbeats and Probing: Two Ways to Gather Evidence

Heartbeats are liveness signals actively sent by the observed node; probing is an active request for a response by the observer. Both can only prove that a specific path succeeded at a specific moment, not that all functions of the node are healthy.

Assume a node sends a heartbeat every 1 second, and the observer marks an anomaly after waiting 3 seconds. A shorter threshold detects real failures earlier but is more likely to misclassify brief pauses as failures; a longer threshold reduces false positives but extends the failover time. Thresholds should be combined with service goals, latency distributions, scheduling pauses, and observation costs, rather than being fixed to always be correct beyond a certain percentile.

Node A observing B's failure does not mean C observing B will necessarily fail. Failure detection results are observer-centric; broadcasting local failures directly as indisputable global facts amplifies local network jitter.

φ-accrual: Separating Anomaly Degree from Action Thresholds

Let the historical heartbeat interval be a random variable $X$, with cumulative distribution function $F$, and let $t$ be the time elapsed since the last heartbeat. The suspicion metric can be defined as:

$$\varphi (t)=-{\log }_{10}(1-F(t))=-{\log }_{10}P(X>t)$$

If the estimated distribution suggests a tail probability of 0.01 that "it still needs to wait this long," then $\varphi =2$; if it is 0.00001, then $\varphi =5$. Larger numbers indicate that the current silence is more anomalous relative to historical behavior. It is not the "posterior probability that the node is dead"; the latter would require failure priors and a more complete statistical model.

The detector is responsible for outputting a continuous suspicion metric, while the upper layer selects thresholds based on different risk levels. For example, removing a load balancer candidate might be sensitive, while triggering expensive data reconstruction might require more evidence. This decoupling is more flexible than a single fixed alive/dead switch. Akka's φ detection documentation demonstrates implementation ideas based on historical intervals.

Distribution estimation also has boundaries: too few samples at startup, long-term load changes, multi-modal network latency, and observer GC pauses can all distort old statistics. The sampling window, minimum variance, startup grace period, and allowed heartbeat pauses are part of the model; one cannot simply copy a single φ threshold.

Why is one observer anxious while another waits, given the same 1200 ms silence?

Using a normal distribution to approximate historical intervals, the average interval is 1000 ms for both. For Link A, the standard deviation is 50 ms, so 1200 ms deviates from the mean by four standard deviations; for Link B, the standard deviation is 300 ms, so the same silence is less than one standard deviation. φ distinguishes the degree of anomaly in these two different contexts.

from math import erfc, sqrt, log10, isclose, inf

def phi(elapsed, mean, stddev, pause_margin=0):
    if elapsed < 0 or stddev <= 0 or pause_margin < 0:
        raise ValueError("Interval and margin must be non-negative, and standard deviation must be positive")
    z = (elapsed - pause_margin - mean) / stddev
    tail = 0.5 * erfc(z / sqrt(2))
    return -log10(tail) if tail else inf

stable = phi(1200, 1000, 50)
variable = phi(1200, 1000, 300)
assert 4.49 < stable < 4.51
assert 0.59 < variable < 0.61
assert stable > 2 and variable < 2
assert isclose(phi(1200, 1000, 50, pause_margin=200), log10(2))
assert phi(1300, 1000, 50) > stable

The code directly uses the complementary error function to calculate the tail, avoiding precision loss from calculating $F$ close to 1 and then subtracting; extremely large intervals may still underflow to zero, in which case infinite suspicion is returned here. The normal distribution is only an approximation, and even assigns a small probability to negative intervals; it should not be treated as a physical law of the network.

This code also does not learn the sample window, set a minimum variance, or implement the startup phase; the threshold of 2 is only used for illustrative comparison, not as a deployment recommendation. Increasing the margin improves tolerance but also delays the detection of real failures; if the observer itself pauses, one cannot claim the problem is solved by modifying the statistics of remote nodes. The Akka documentation explains the impact of historical mean, variance, and acceptable pauses on the curve. φ Detector Documentation

Phi is a log tail probability, not death probability

The shaded tail is the historical model’s probability that the next heartbeat has not arrived. Keep silence at 1200 ms and widen the standard deviation: phi drops although the observation is unchanged. The reference distribution changes, not the peer’s actual health. With a fixed distribution, longer silence shrinks the tail and increases its negative logarithm. The plot is cropped; values use the full normal approximation.

SWIM: Division of Labor Between Detection and Membership Propagation

SWIM uses random probing and, after direct probing fails, relies on other members to probe the target, reducing false positives caused by a single anomalous path. Indirect probing does not require all mediators to succeed; any valid ACK can provide evidence.

The suspicion phase gives live nodes the opportunity to refute outdated judgments, and then propagates the results via membership updates. Version information such as member incarnation is used to distinguish new liveness claims from old suspicions, preventing any old ACK from permanently overwriting newer states. SWIM Original Paper clearly separates failure detection from membership update propagation.

SWIM and φ are different designs: the former describes the probing and propagation protocol, while the latter describes the statistical suspicion calculation. They can be combined in some systems, but SWIM cannot be defined as "combining φ with gossip."

Full-mesh heartbeats send $O(N)$ messages per node per round, totaling $O(N^2)$ for the whole group. Fixed probing fan-out can keep the number of probe messages per node at a constant order, but member lists, propagation payloads, retransmissions, and tail latency of failure discovery must still be accounted for separately; one cannot deduce that the entire system cost is constant from $O(1)$ probing.

Who Has the Right to Take Over After Anomaly Detection

The detector saying "suspect the old master is unreachable" does not mean the old master has stopped. If the new master starts writing to the database, and the old master continues writing after recovering, there may be two operational sources simultaneously.

Safe takeover usually requires authority granted by a consensus or lease protocol, and requires the protected resource to check generation information such as fencing tokens. The detector accelerates the decision to suspect; the permission protocol prevents outdated instances from remaining effective. Even if the detector occasionally misjudges, the latter should protect safety.

This is consistent with the distinction in Fault Models: safety cannot rely solely on an empirical timeout that never misjudges.

Fencing must be checked on the resource side and occur atomically with the write

Assume the authorization service issues tokens 41 and 42 in sequence. The old master holds 41, pauses, and then recovers; the new master holds 42. The resource saves the maximum token it has seen and rejects smaller generations during writes. The example below uses sequential function calls to represent the atomic "compare generation and write," without implementing the authorization service or database transactions.

class Resource:
    def __init__(self):
        self.highest = 0
        self.value = None

    def write(self, token, value):
        if token < self.highest:
            return False
        self.highest, self.value = token, value
        return True

r = Resource()
assert r.write(41, "old")
assert r.write(42, "new")
assert not r.write(41, "late-old")
assert r.value == "new"
assert r.write(42, "new-again")  # Multiple operations allowed within the same authorization period

# A new token that has been issued but not yet reached the resource will not automatically change the resource's check state.
r2 = Resource()
assert r2.write(41, "old")
issued_token = 42
assert r2.write(41, "late-but-before-fence")
assert r2.write(issued_token, "new")
assert not r2.write(41, "now-rejected")

The second group of calls defines the guarantee: once the resource sees 42, 41 can no longer overwrite it; merely issuing 42 does not instantly notify all external resources. If the requirement is to reject any old writes immediately after authorization switches, the resource must participate in this switch or atomically verify the current authorization state; one cannot rely solely on the "maximum seen token." The write-side mechanism of fencing can be found in Martin Kleppmann's analysis of expired lock holders.

Real tokens must be issued monotonically by a trusted authorization protocol; resources cannot allow arbitrary clients to self-report a huge number. Resources must also persistently save the generation and place the check and business modification in the same atomic operation; if the lock is released before writing the value after the check passes, old and new requests can still interleave. For duplicate deductions within the same token, request ID deduplication is still needed: fencing isolates outdated generations, idempotency eliminates retries of the same operation, and the two do not replace each other.

Deadlines, Timeouts, and Recovery Budgets

A request has a total deadline, and each downstream operation can only use the remaining budget. If A has already spent 80 ms and the total budget is 100 ms, giving B an independent 100 ms timeout would break the caller's promise. After a timeout, cancellation must also be propagated to avoid expired work continuing to occupy resources.

Retries also consume budget and capacity. Exponential backoff and jitter can distribute retries, but they cannot replace rate limiting, idempotency, and overload protection. Member loss timeouts, RPC deadlines, and health check thresholds serve different decisions and should not share a single "global timeout constant."

References

• SWIM Paper
• Akka: Phi Accrual Failure Detector
• Gossip Protocol
• Service Discovery

Keywords: heartbeat, timeout, φ-accrual, SWIM, indirect probe, suspicion, incarnation, fencing, deadline