Fail-stop

Schlichting and Schneider defined a fail-stop processor by two visible effects of a failure: the processor stops executing, and its internal state and volatile memory are lost. Remaining storage is stable storage: it is unaffected by the failure and can be read by other processors. A failure is any behavior that is inconsistent with the processor's specified instruction semantics.

Schneider later stated the same idea as three properties:

• Halt on Failure. The processor halts instead of performing an erroneous state transformation that would be visible to other processors.
• Failure Status. Any processor can detect that another has failed and therefore halted.
• Stable Storage. Storage is partitioned into stable storage, which survives a failure and is readable by any processor, and volatile storage, which is lost and is not accessible to others.

A program interrupted by a failure can be restarted on a working fail-stop processor. Because volatile state is gone, a recovery protocol kept in stable storage must finish or repair the interrupted action from a well-defined stable state. Schneider wrote that an application that needs N processors when none fail can tolerate up to f fail-stop failures with N + f such processors: survivors detect a halt and continue the work from stable storage, provided enough capacity remains to meet timing constraints.

Kenneth P. Birman distinguished fail-stop failures from ordinary halting or crash failures. In both models a process either runs correctly or stops without taking incorrect actions. In the crash model, others typically infer the halt only by timeouts or missing keep-alive messages. In the fail-stop model they have an accurate way to detect the failure, for example a timeout that occurs only if the monitored process has actually crashed. Birman called that detection assumption optimistic and noted that solutions under it still have to be related to real systems in which detection can be wrong.

Schneider observed that some protocols replace the Failure Status Property with timeouts, which requires synchronized clocks. Without that assumption two processors might disagree about whether a third has halted. Some protocols also omit stable storage and replicate state at other processors, which he treated as an approximation of the Stable Storage Property.

Byzantine faults, by contrast, place no restriction on a faulty component's behavior. A failed node may send arbitrary or conflicting messages, including messages that make it look correct to some observers. Fail-stop is the simpler case: there are no erroneous outputs to vote away, only a detected halt.

In Schneider's tutorial on state machine replication, an ensemble that must tolerate t Byzantine faults needs at least 2t + 1 replicas, with majority output. If processors suffer only fail-stop failures, t + 1 replicas suffice, and the ensemble may use the output of any remaining replica, because a fail-stop processor does not emit a wrong result and one correct replica remains after t failures.

Schlichting and Schneider argued that complete fault tolerance with finite hardware is impossible, so the engineering goal is to tolerate a bounded number of failures of a stated kind. Their method is to write software as if fail-stop processors exist, then implement an approximation of those processors.

A k-fail-stop processor behaves like a fail-stop processor unless k + 1 or more of its components fail. One construction interconnects real processors and memories and uses a solution to the Byzantine Generals Problem so that nonfaulty units agree on values read from replicated stable storage. Disagreement signals a failure and the nonfaulty processors halt. Schlichting and Schneider used 2k + 1 processors so that up to k faults can be tolerated in that comparison. Schneider's 1984 design splits the approximation into k + 1 program processes that run the workload and 2k + 1 storage processes that hold copies of stable storage, with writes agreed so that a disagreement among program processes is visible to storage processes.

They noted that highly reliable multiprocessors such as FTMP and SIFT could be configured to approximate a collection of fail-stop processors, because both already replicate processors and memory. Schneider wrote that most protocols for fault-tolerant systems already assume fail-stop processors or an equivalent, which is a reason to study how expensive it is to implement the abstraction rather than to assume it.

In cryptography, a fail-stop signature is a digital signature scheme in which a signer can prove that a forged signature was not produced under the scheme's secret key, typically against a computationally unbounded forger, after which the signer can stop using the key. That primitive is unrelated to the processor failure model.