Systematic incorporation of efficient fault tolerance in systems ofcooperating parallel programs

摘要

Cooperating parallel programs are being increasingly used incritical applications that require both high performance and highreliability. A promising technique for simultaneously achieving theseobjectives is to embed the fault tolerance within the program instead ofsuperimposing it via external mechanisms. We develop one such approachfor a group of processes that cooperate via shared data structures. Thescheme uses data structures having two or more invariant assertions.When the strong invariant is true, the performance is good. When it isfalse, the performance may be adversely affected, but it is guaranteedthat the system will operate correctly provided the weak invariant istrue. The algorithms are designed to ensure that processor failures willnever cause the weak invariant to be false and to restore the stronginvariant within a finite number of recovery actions. We develop arobust task handling mechanism to support the approach and illustrate itfor three common data structures