Automation of
Fault-tolerant Graceful Degradation
Yiyan Lin, Sandeep Kulkarni, Arshad Jhumka
Abstract
Traditionally, (nonmasking and masking) faulttolerance has focused on ensuring that after the
occurrence of faults, the program recovers to states from where it continues to
satisfy its original specification. However, a problem with this limited notion
is that, in some cases, it may be impossible to recover to states from where
the entire original specification is satisfied. For this reason, one can
consider a fault-tolerant graceful-degradation program that ensures that upon
the occurrence of faults, the program recovers to states from where a (given)
subset of its specification is satisfied. Typically, the subset of
specification satisfied thus would be the critical/important requirements.
In this paper, we initially focus on automatically
revising a given fault-intolerant program into a fault-tolerant gracefully
degrading program. Specifically, we propose a two-step approach: In the first
step, we transform the fault-intolerant program into a graceful program. This
program is guaranteed to satisfy only the given subset of specification (e.g.,
critical requirements). In particular, this step involves adding new behaviors
that will satisfy the given subset of the specification. The second step
involves utilizing the original program and the graceful program to obtain a
fault-tolerant gracefully degrading program. We also develop an algorithm to
transform the gracefully degrading program into a distributed gracefully
degrading program. Afterwards, the second phase of our transformation can be
applied to generate a distributed fault-tolerant gracefully degrading program.
We showcase the algorithm with three different non-trivial case studies.
Finally, we formalize the problem of multi-graceful degradation and propose an
algorithm that solves it and we use a complex case study to showcase the
viability of the approach. All the
algorithms have polynomial time complexity in the size of the state space of
the original program.
Paper:
Return to the publication list
Return to the Sandeep's home page