Correlated Timeouts and Detection Storms When Every Monitor Sees the Same Fault

The argument for gossip and for multi-observer detection rests on a probability claim: many independent weak observations combine into one strong conclusion. That claim is sound only when the observations are independent. In a real cluster the most damaging faults are exactly the ones that hit many observers at once, and the combination then produces a confident verdict that is confidently wrong.

The independence assumption, stated plainly

Take m observers each of which declares a peer failed with false-positive probability q per decision window. If the observers’ errors were independent and a system required, say, a majority to agree, the probability that a healthy peer is removed would be the sum over the upper tail of a binomial with parameters m and q. With m = 5 and q = 0.01, a three-of-five rule gives about 10^-5 per window. The arithmetic is the standard redundancy argument.

Now drop independence. Suppose a single cause, such as a top-of-rack switch dropping packets or a storage backend stalling, makes every observer’s decision fail simultaneously, so the errors are perfectly correlated. The probability that a majority agrees is then just q, not q^3-ish. Five observers bought nothing at all. Worse, they bought the appearance of consensus: the system now has five independent confirmations of a wrong fact, and any downstream logic that weighs agreement will trust it more than a single report.

This is why the phrase “two independent observers” in a design document should always be followed by a question about what makes them independent. If both observers are processes on the same host, they share the host’s pause. If both are in the same rack, they share the rack’s switch. If both heartbeat over the same overlay network, they share its control plane. Independence is a property of the failure modes, not of the process count.

How a shared pause manufactures agreement

The most common correlated cause is not a network fault but a scheduling one. A hypervisor deschedules a set of virtual machines that share a physical core, or a stop-the-world collector runs in several processes that were started together with the same heap settings, or a cron-like job fires across a fleet at the same wall-clock second. The result is that many processes stop responding in the same interval, and every monitor watching them times out in the same interval.

The monitors themselves may be the ones pausing. A monitor that shares the stalled storage backend cannot evaluate its own timers, so it wakes up with a batch of overdue deadlines and evaluates them all at once. The evaluation sees a large gap for every peer it watches, and a fixed-threshold detector declares all of them failed. One pause becomes n suspicions in one tick. The mechanism is described from the peer’s side in pause-induced false suspicion; here the point is the multiplication.

Detection storms have a second-order form that is worse. The suspicion traffic itself becomes load. A node that declares many peers dead gossips many updates; the recipients process them and update their own views; some recipients now believe the cluster has shrunk and may trigger rebalancing, which moves data, which adds load, which lengthens the pauses that caused the storm. The feedback loop is the reason a brief pause can produce a long outage, and it is why the storm is a distinct failure mode rather than an amplified false positive.

Randomizing the timeout: what it fixes and what it does not

The standard remedy is jitter. If every monitor uses the same timeout and the same phase, then a periodic disturbance that arrives on a fixed schedule hits them all in the same window. Randomizing each monitor’s interval and phase decorrelates the sampling, so a disturbance shorter than the jitter range is caught by only a fraction of monitors.

What jitter fixes is phase alignment. If the disturbance is periodic with period P and each monitor’s window is offset uniformly in [0, P), then the fraction of monitors whose window overlaps the disturbance is proportional to the disturbance’s duration divided by P, not all of them. That is a real improvement, and it costs nothing but a random offset.

What jitter does not fix is a disturbance longer than the window. If the pause lasts longer than every monitor’s timeout regardless of phase, every monitor declares failure no matter how the phases are arranged. Jitter decorrelates the sampling instant; it cannot decorrelate a cause that outlasts the sample. For that, the timeout has to be longer than the cause, or the detector has to distinguish “the peer did not answer” from “I could not evaluate the answer”, which requires a local liveness signal that does not depend on the network.

The other limit on jitter is that it must not be applied to the detection budget. Adding a uniform random offset of up to a full interval to a timeout doubles the worst-case detection latency. The offset is usually applied as a fraction of the interval, small enough to decorrelate phases and small enough not to matter for latency, and the two constraints bracket the choice.

Backoff as storm control

A monitor that has just declared a peer dead should not immediately declare it dead again. The natural policy is exponential backoff on repeated suspicions of the same peer: the first declaration triggers a probe schedule at the base interval, and each subsequent failure doubles the interval up to a cap. This converts a storm from a fixed rate of messages into a decaying one and gives the peer time to recover before the next evaluation.

The cost is detection latency for a peer that fails, recovers, and fails again. Backoff cannot distinguish “still dead” from “back and dead again”, so a genuinely flapping peer is detected progressively more slowly. The standard mitigation is to reset the backoff on any successful contact, which means the backoff only grows while the peer is continuously unresponsive, and a single successful probe restores the base rate. That reset is also an attack surface in the sense that a peer that answers one probe in ten keeps the monitor at the base rate forever, which is a real behaviour worth knowing about when a service is degraded rather than down.

Quarantine instead of removal

The structural fix for correlated false positives is to make the response to suspicion reversible and cheap. If a false declaration removes a node from a quorum, the damage is immediate and may be unrecoverable. If a false declaration merely stops routing new work to the node while keeping its membership and its data, the damage is a temporary dip in capacity and the recovery is automatic when the node answers again.

This is why graded suspicion levels are useful beyond their statistical role. A detector that reports a continuous level, as in phi accrual from arrival statistics, can drive a quarantine that engages before any irreversible action. The rule to encode is that irreversible actions require evidence that does not collapse when a shared cause appears, and such evidence has to come from failure domains that do not share a cause.

Concretely, that means observers on different power feeds, different racks, or different network planes, and a rule that requires agreement across domains rather than across processes. It also means the detector’s own configuration should be heterogeneous: identical timeouts across a fleet are a correlation waiting to happen, and identical timeouts on identical hardware running identical software is the worst case, because the workloads pause together.

Measuring correlation is harder than measuring error rate

A detector’s false-positive rate is observable: count the declarations where the peer later answered. Its correlation structure is not, because the counterfactual, what would have happened without the shared cause, is unavailable. The practical proxy is to record, for each declaration, the set of other declarations in the same window, and to look for windows where many peers were declared simultaneously.

A cluster where declarations arrive in bursts is a cluster with a correlated cause, regardless of the total rate. A cluster where declarations arrive singly, at a rate consistent with the per-peer arithmetic in heartbeat interval and timeout arithmetic, is behaving as the independent model predicts. The distinction is more useful than the aggregate rate, because the aggregate can look acceptable while every declaration is part of a burst that removes a large fraction of the cluster at once.

The final implication is about thresholds. A threshold chosen to give an acceptable per-peer false-positive rate is not automatically acceptable at the cluster level, because the events are correlated. The cluster-level question is the probability that a single cause removes enough peers to break a quorum or a replication factor, and that probability is governed by the size of the shared failure domain, not by the number of observers.