Complexity Analysis of Weak Multitolerance
Jingshu Chen and Sandeep S. Kulkarni
Abstract
In this paper, we classify multitolerant
systems, i.e., systems that tolerate multiple
classes of faults and provide potentially
different levels of tolerance to them in terms
of \strong and \weak multitolerance.
Intuitively, this classification is based upon
the guarantees provided by the program when one
class of faults occurs while it is recovering
from another class of faults. We focus on
automated synthesis of \weak multitolerant
programs. Such \weak multitolerance becomes
necessary when it is impossible to provide
\strong multitolerance and/or when the
probability of one class of faults occurring
while the program is `recovering' from a fault
from another class is negligible.
By considering the levels of fault-tolerance
provided to each class of faults, we evaluate
five possible combinations for \weak
multitolerance. We find a counterintuitive
result that if masking fault-tolerance is
desired for one class of faults and masking (or
failsafe) fault-tolerance is desired for
another class of faults then the problem is
NP-hard. This result is surprising since the
corresponding problem for \strong
multitolerance can be solved in polynomial
time. Also, we show that the problem of
synthesizing \weak multitolerance for other
combinations is in P.
More broadly, this result demonstrates the role
of assumptions, e.g., independence of
occurrences of faults from different classes,
in the complexity of automated synthesis.
Paper:
Return to the
publication list
Return
to the Sandeep's home page