Enhancing The Fault-Tolerance of Nonmasking Programs

Sandeep S. Kulkarni and Ali Ebnenasir

Abstract

In this paper, we focus on automated techniques to enhance the fault-tolerance of a nonmasking fault-tolerant program to masking. A masking program continually satisfies its specification even if faults occur. By contrast, a nonmasking program merely guarantees that after faults stop occurring, the program recovers to states from where it continually satisfies its specification. Until the recovery is complete, however, a nonmasking program can violate its (safety) specification. Thus, the problem of enhancing fault-tolerance from nonmasking to masking requires that safety be added and recovery be preserved. We focus on this enhancement problem for high atomicity programs --where each process can read all variables-- and for distributed programs --where restrictions are imposed on what processes can read and write. We present a sound and complete algorithm for high atomicity programs and a sound algorithm for distributed programs. We also argue that our algorithms are simpler than previous algorithms, where masking fault-tolerance is added to a fault-intolerant program. Hence, these algorithms can partially reap the benefits of automation when the cost of adding masking fault-tolerance to a fault-intolerant program is high. To illustrate
these algorithms, we show how the masking fault-tolerant programs for triple modular redundancy and Byzantine agreement can be obtained by
enhancing the fault-tolerance of the corresponding nonmasking versions. We also discuss how the derivation of these programs is simplified when we begin with a nonmasking fault-tolerant program.

Paper:

Slides 

BibTeX Entry

@Article{ke03,  

 author =       {S.~S.~Kulkarni and A.~Arora},   

title =        {Enhancing The Fault-Tolerance of Nonmasking Programs},  

 journal =      {International Conference on Distributed Computing Systems},   

year =         {2003},   

OPTkey =       {},   

OPTvolume =    {},   

OPTnumber =    {},   

OPTpages =     {},   

OPTmonth =     {},   

OPTnote =      {},  

 OPTannote =    {} 

}

 
Return to the publication list
Return to the Sandeep's home page