Questions: Failure Detection with Heartbeats

Question 1

A team sets their heartbeat timeout to 100ms to detect node failures as quickly as possible. Their operations team starts receiving many 'node down' alerts that resolve within seconds. What is the most likely root cause?

• A. The nodes are actually crashing and recovering — 100ms is appropriate for detecting this
• B. The timeout is too short: brief network congestion or processing spikes cause heartbeats to arrive late, triggering false positives
• C. The heartbeat interval itself should be shortened to match the timeout
• D. Gossip-based heartbeats would eliminate this problem entirely without any tradeoff

Answer: (B)

Short timeouts improve detection latency for real failures but increase the false positive rate — declaring a live node dead because a heartbeat was delayed by transient network congestion, a garbage collection pause, or a busy CPU. This is the core detection-speed vs. accuracy tradeoff. The false positive storm is a classic symptom of an overly aggressive timeout. Gossip-based approaches (option D) reduce overhead but do not eliminate the fundamental timeout tradeoff.

Question 2

A node in a distributed system hasn't received a heartbeat from a peer for three times the normal interval. The network is experiencing unusual congestion. What can the observing node definitively conclude?

• A. The peer has crashed and should be marked as failed immediately
• B. The peer is experiencing a Byzantine failure and may be sending corrupt messages
• C. Nothing definitive — in an asynchronous network, missing heartbeats cannot distinguish a crashed node from a very slow one
• D. The peer has definitely not crashed but needs its heartbeat interval increased

Answer: (C)

This is the fundamental impossibility result: in an asynchronous network (no upper bound on message delivery time), no timeout value can definitively distinguish a crashed node from one that is alive but slow. The missing heartbeats could be caused by a crash, by severe congestion delaying messages, or by the peer being overloaded. A perfect failure detector — one that is both complete (detects all failures) and accurate (never makes false accusations) — is provably impossible in the asynchronous model. Real systems must accept this and design for graceful handling of both false positives and false negatives.

Question 3

In a fully synchronous network where message delivery time is bounded by a known maximum delay δ, it is theoretically possible to build a perfect failure detector.

• T. True
• F. False

Answer: True

True. The impossibility result applies specifically to asynchronous networks, which have no upper bound on message delay. If you know that any message will arrive within δ time units, you can set a timeout of δ + ε and be certain: if a heartbeat hasn't arrived by then, the node has truly crashed (not merely slow). The synchrony assumption is what makes the distinction between 'crashed' and 'slow' detectable. Real-world networks are asynchronous, which is why the impossibility matters in practice.

Question 4

Heartbeat-based failure detection can definitively identify whether a node has crashed or is merely slow, as long as the timeout is calibrated correctly.

• T. True
• F. False

Answer: False

False. No timeout calibration overcomes the fundamental impossibility in an asynchronous network. Even a perfectly tuned timeout only reduces false positives — it cannot eliminate them, because network behavior is unbounded. A node that takes 10 seconds to respond is indistinguishable from a crashed node during those 10 seconds. The impossibility result (proved by Fischer, Lynch, and Paterson for consensus, extended to failure detection) shows that in an asynchronous model, completeness and accuracy cannot both be guaranteed simultaneously.

Question 5

Why do systems like Cassandra use phi accrual failure detectors rather than simple binary timeout-based heartbeats?

Model answer: Phi accrual detectors replace the binary alive/dead verdict with a continuous suspicion score (φ) based on the statistical distribution of recent heartbeat arrival times. If heartbeats from a node normally arrive every 500ms with low variance, and the last one was 3 seconds ago, φ is very high. If the network is normally variable (high jitter), the same 3-second gap produces a lower φ. This adaptive approach avoids the fixed-threshold problem: a timeout that works under normal conditions may generate false positives during congestion or false negatives if the network slows down. Systems can then set different response thresholds for different actions — e.g., 'log a warning' at φ=5, 'route around' at φ=8, 'declare dead' at φ=12.

The phi accrual approach treats heartbeat arrival times as a statistical process and measures the probability that the observed gap is due to failure rather than normal variation. This makes the detector self-calibrating: it learns the typical behavior of each link and computes suspicion relative to that baseline. It reduces both false positives (during congestion) and detection latency (when failure actually occurs), at the cost of complexity.