Masking Faults While Providing Bounded-Time Phased Recovery

Borzoo Bonakdarpour and Sandeep S. Kulkarni

Abstract

We focus on synthesis techniques for transforming existing fault-intolerant real-time programs to fault-tolerant programs that provide \emph{phased recovery}. A fault-tolerant program is one that satisfies its \emph{safety} and \emph{liveness} specifications as well as \emph{timing constraints} in the presence of faults. We argue that in many commonly considered programs (especially in mission-critical systems), when faults occur, simple recovery to the program's normal behavior is necessary, but not sufficient. For such programs, it is necessary that recovery is accomplished in a sequence of phases, each ensuring that the program satisfies certain properties. In this paper, we show that, in general, synthesizing fault-tolerant real-time programs that provide bounded-time phased recovery is NP-complete. We also characterize a sufficient condition for cases where synthesizing fault-tolerant real-time programs that provide bounded-time phased recovery can be accomplished in polynomial-time in the size of the input program's region graph.

Paper:

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