Heartbeat Interval and Timeout Arithmetic for Fixed-Threshold Detectors

The simplest failure detector is a counter. A monitored process sends a message every interval; the monitor holds a deadline, and if the deadline passes with no message it declares the sender dead. Two numbers configure it: the interval between beats and the number of beats that may be missed before the declaration. Everything else about the detector’s behaviour, including how often it is wrong and how fast it is right, follows from those two numbers and from a property of the network that the numbers do not control.

The three quantities the two numbers set

Write I for the heartbeat interval and k for the threshold, so the effective timeout is T = k·I. Three quantities move when either number moves.

Detection latency for a genuine crash is between T - I and T. The declaration fires at T after the last beat that arrived, and the crash happened somewhere between that beat and the next one that never came, so the latency is the timeout minus however far into the interval the crash fell. Halving T halves detection latency.

Message volume per monitored pair is 1/I messages per second. For a full mesh of n processes each monitoring every other, the aggregate is n(n-1)/I messages per second, which grows quadratically. A hundred processes beating every second produce just under ten thousand messages per second; at roughly a hundred bytes each including framing, that is on the order of a megabyte per second of pure liveness chatter, and a thousand processes produce a hundred times that. This is the reason large clusters do not use full-mesh heartbeats and instead use the designs in gossip-based suspicion propagation or aggregation layers.

False-positive probability is where the two numbers interact nonlinearly, and it is the quantity most often set by accident.

Why the tail, not the average, decides the threshold

A monitor declares failure after k consecutive beats fail to arrive within T. Let q be the probability that a single beat takes longer than T to arrive, counting a beat that is dropped as taking forever. Assuming beats are independent, the probability that a given decision window produces a false declaration is q^k, and since a window is evaluated every T seconds, the rate of false declarations per monitored process is roughly q^k / T.

The exponentiation is the entire design. A detector with k = 3 does not need the network to be three times better than a detector with k = 1; it needs the network’s tail probability to be better by whatever factor makes the cube small. Take a link where 99.9 percent of beats arrive within the timeout, so q = 10^-3. With k = 5, q^k = 10^-15, and a declaration rate near 2·10^-16 per second per process, which over a ten-thousand-process cluster is still one false suspicion per ten thousand years or so. Now take a link where 99 percent arrive in time, q = 10^-2. With the same k = 5, the rate is 2·10^-11 per second per process, and ten thousand processes produce a false suspicion every couple of months. At k = 5 one extra nine in the tail bought five orders of magnitude, and losing one nine gave the same five back.

The practical lesson is that the mean round trip is nearly irrelevant to threshold selection. A network with a 1 millisecond median and a 400 millisecond 99.9th percentile is a network whose timeout must be above 400 milliseconds, because a threshold of a few milliseconds would fire on the tail constantly. This is the same argument as the tail-at-scale observation about fan-out: with enough independent requests, the slowest one in the batch is drawn from the far tail of the distribution, so the tail becomes the typical case.

Setting k from a target, not from intuition

The rate formula inverts cleanly. For a target false-declaration rate λ per process per second, the required tail probability is q = (λ·T)^(1/k). A cluster of n processes wanting at most one false suspicion per year overall needs λ = 1/(n · 3.15·10^7). With n = 1000 and T = 5 seconds, that is λ ≈ 3·10^-11, so λ·T ≈ 1.6·10^-10, and with k = 5 the requirement is q ≈ 0.011: about one beat in ninety may exceed five seconds. With k = 3 the requirement tightens to q ≈ 5·10^-4, and with k = 8 it loosens to about 0.06. Doubling k roughly squares the tolerance for the tail.

Two assumptions in that arithmetic do not hold in practice, and both push the real rate above the prediction.

Beats are not independent. A garbage collection pause, a hypervisor steal, a congested queue, or a route change affects several consecutive beats at once. The model above assumes each miss is a fresh coin flip, but a correlated stall produces k misses from a single cause, so the effective q is the probability of a stall lasting longer than T, not the probability that one beat is late. Long stalls are far more common than q^k suggests, which is why a detector with a large k still fires when a process blocks for seconds at a time. Stop-the-world pauses and observer-side suspicion covers the mechanism.

The window is a run, not a rate. The formula treats each decision window independently, but the detector re-evaluates continuously, so overlapping windows of k beats are highly correlated. The clean way to state the guarantee is in terms of the interval between successful beats: a declaration occurs only when the gap exceeds T, so the false-positive rate is bounded by the probability that a single inter-arrival gap exceeds T. That restatement is stricter and more useful, because it makes clear that the detector is measuring one gap, and the threshold should be chosen against the distribution of gaps rather than the distribution of individual messages.

Detection latency is not the same as failover time

Lowering T improves detection and worsens accuracy, but the system-level latency to recovery includes more than detection. After the declaration, the failure has to be disseminated, the replacement has to be chosen, and the clients have to be redirected. A detector tuned to a one-second timeout in a system whose failover takes thirty seconds has optimized the small term.

There is a matching asymmetry on the other side. When the suspected process is alive, the system must undo the declaration. Undoing is usually slower than declaring, because the live process has to prove liveness in a way the monitor accepts as current rather than stale. A protocol that lets a restarted process reclaim its identity by sending a heartbeat will flap forever if the monitor’s view of the incarnation is behind, which is why incarnation numbers rather than bare liveness proofs carry the refutation in SWIM, as described in suspicion and incarnation refutation.

A reasonable default structure, stated as a rule of thumb rather than a measurement: set T to at least the observed 99.9th percentile of gap lengths under load, set k so that T/I gives a run length whose correlated-stall probability is acceptable, and confirm that T plus dissemination plus failover is under the availability target. The first constraint usually dominates and usually forces T well above what the median suggests.

Where fixed thresholds break down

A fixed threshold is a claim that the delay distribution is stationary. On a network that is stable for months and congested for minutes, the threshold must be sized for the congestion, which makes it too slow during the stable periods. On a network whose load varies by an order of magnitude across the day, no single threshold is right at both ends.

Two escapes exist. The first is to make T a function of observed history, which is the accrual approach: compute the probability that the process is alive given the current gap and the recent distribution of gaps, and report a continuous suspicion level rather than a binary one. That converts the tuning problem into a sensitivity parameter and is the subject of phi accrual from arrival statistics.

The second is to stop making each monitor responsible for the whole truth. If suspicion is a local opinion that gets disseminated and reconciled, a single monitor’s threshold can be loose without stalling the system, because other observers contribute independent evidence. That design also creates the opposite problem, where many observers agree on a wrong conclusion for a correlated reason, which is covered in correlated timeouts and detection storms.

Either way, the arithmetic above remains the baseline. Any adaptive scheme is still choosing how many consecutive misses to tolerate, just doing it with a model instead of a constant, and the tail of the gap distribution still decides the answer.