Fail-stop

This article is about the failure model in distributed computing. For software that reports errors immediately, see Fail-fast system.

In distributed computing, a fail-stop failure is a failure model in which a processor or process stops executing instead of performing an incorrect state change that other components could observe. The halt is detectable by other processors, and a designated portion of storage remains readable after the failure. Richard D. Schlichting and Fred B. Schneider introduced the fail-stop processor as a programming abstraction for building fault-tolerant computer systems in 1983.

The model sits at the mild end of a spectrum of failure assumptions that also includes silent crash (halting) failures and Byzantine faults. It is an idealization. A perfect fail-stop processor cannot be built with a finite amount of hardware, because enough faults could disable every error detector. Practical designs therefore approximate it with a k-fail-stop processor that behaves as specified unless more than k component failures occur.

Definition

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.

Relation to other models

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.

Implementation

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.

Other uses

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.

See also

• Byzantine fault
• Failure detector
• Fault tolerance
• Fail-fast system
• State machine replication
• Exception handling