Automating the Addition of Fault-Tolerance

Sandeep S. Kulkarni and Anish Arora

Abstract

In this paper, we focus on automating the transformation of a given fault-intolerant program into a fault-tolerant program. We show how such a transformation can be done for three levels of fault-tolerance properties, failsafe, nonmasking and masking. For the high atomicity model where the program can read all the variables and write all the variables in one atomic step, we show that all three transformations can be performed in polynomial time in the state space of the fault-intolerant program. For the low atomicity model where restrictions are imposed on the ability of programs to read and write variables, we show that all three transformations can be performed in exponential time in the state space of the fault-intolerant program. We also show that the the problem of adding masking fault-tolerance is NP-hard and, hence, exponential complexity is inevitable unless $P\!=\!NP$.  

Paper:

Slides

BibTeX Entry

  
@Article{ftrtft2000,
  author =       {S.~S.~Kulkarni and A.~Arora},
  title =        {Automating the Addition of Fault-Tolerance},
  journal =      {Formal Techniques in Real-Time and Fault-Tolerant Systems},
  year =         {2000},
  OPTkey =       {},
  OPTvolume =    {},
  OPTnumber =    {},
  OPTpages =     {},
  OPTmonth =     {},
  OPTnote =      {},
  OPTannote =    {}
}
Return to the publication list
Return to the Sandeep's home page