Systematic incorporation of efficient fault tolerance in systems of cooperating parallel programs

Cooperating parallel programs are being increasingly used in critical applications that require both high performance and high reliability. A promising technique for simultaneously achieving these objectives is to embed the fault tolerance within the program instead of superimposing it via external mechanisms. We develop one such approach for a group of processes that cooperate via shared data structures. The scheme uses data structures having two or more invariant assertions. When the strong invariant is true, the performance is good. When it is false, the performance may be adversely affected, but it is guaranteed that the system will operate correctly provided the weak invariant is true. The algorithms are designed to ensure that processor failures will never cause the weak invariant to be false and to restore the strong invariant within a finite number of recovery actions. We develop a robust task handling mechanism to support the approach and illustrate it for three common data structures.<>