Complexity Issues in Automated Synthesis of Failsafe Fault-Tolerance
Sandeep S. Kulkarni and Ali Ebnenasir
Abstract
We focus on the problem of synthesizing failsafe fault-tolerance where fault-tolerance is added to an existing (fault-intolerant) program. A failsafe fault-tolerant program satisfies its specification (including safety and liveness) in
the absence of faults. However, in the presence of faults, it
satisfies its safety specification. We present a somewhat
unexpected result that, in general, the problem
of synthesizing failsafe fault-tolerant {\em distributed} programs from their fault-intolerant version is NP-complete in the state space of the program. We also identify a class of specifications, {\em monotonic specifications} and a class of programs, {\em monotonic programs} for which the synthesis of failsafe fault-tolerance can be done in polynomial time (in program state space).
As an illustration, we show that the monotonicity restrictions are met
for commonly encountered problems such as
Byzantine agreement, distributed consensus, and atomic commitment.
Furthermore, we evaluate the role of these restrictions in the complexity of synthesizing failsafe fault-tolerance. Specifically, we prove
that if only one of these conditions is satisfied,
the synthesis of failsafe fault-tolerance is still NP-complete. Finally, we demonstrate the application of monotonicity property in enhancing the fault-tolerance of (distributed) nonmasking fault-tolerant programs to masking.
Paper:
Return to the publication list
Return to the Sandeep's home page