Fail-stop as a purchased assumption

How is fail-stop bought, and why can its false-positive rate never reach zero?

Fail-stop means a component either works correctly or stops completely and detectably. It is the assumption under essentially every distributed algorithm. It is very convenient: failure becomes a discrete event, recovery becomes a discrete action, and the failure detector's job becomes trivial.

Nothing in nature provides it. Engineering provides it:

• a watchdog that kills a process that misses a deadline,
• a supervisor that restarts a process after a failed health check,
• a node that kills itself ("suicides") when it loses its lease (its time-limited permission to act).

Each of these is a deliberate conversion of a degraded component into a dead one. You destroy capacity in order to obtain decidability. That trade is the right one and it is rarely described as a trade. It can also go wrong in its own way: on Mars Pathfinder a watchdog that worked correctly turned a priority inversion into a reboot loop.

The detector sits on one curve with two error modes

Since the detector is a timeout, it sits on a single trade-off curve with two error modes and no third option.

• Too short: false positives. They eject healthy nodes, which reduces capacity, which raises latency, which creates more false positives. That is a feedback loop, with the health-check system supplying the gain.
• Too long: false negatives. They leave a degraded node in service. That is the rest of this article.

Phi-accrual detectors and adaptive thresholds do not escape the curve. A phi-accrual detector computes a suspicion level from the history of heartbeat arrival times, instead of a yes/no answer after a fixed time. These approaches move along the curve more intelligently, by making the threshold depend on the observed variance instead of being a constant.

What does this system assume that it cannot verify? That silence means death. Who pays when it is wrong? If it is wrong in the direction of "dead", the system pays in capacity. If it is wrong in the direction of "alive", the clients pay in latency, and clients are outside the system's measurement boundary.