Paper Info
Title
The complexity of automated addition of fault-tolerance without explicit legitimate states
Abstract
Existing algorithms for automated model repair for adding fault-tolerance to fault-intolerant models incur an impediment that designers have to identify the set of legitimate states of the original model. This set determines states from where the original model meets its specification in the absence of faults. Experience suggests that of the inputs required for model repair, identifying such legitimate states is the most difficult. In this paper, we consider the problem of automated model repair for adding fault-tolerance where legitimate states are not explicitly given as input. We show that without this input, in some instances, the complexity of model repair increases substantially (from polynomial-time to NP-complete). In spite of this increase, we find that this formulation is relatively complete; i.e., if it was possible to perform model repair with explicit legitimate states, then it is also possible to do so without the explicit identification of the legitimate states. Finally, we show that if the problem of model repair can be solved with explicit legitimate states, then the increased cost of solving it without explicit legitimate states is very small. In summary, the results in this paper identify instances of automated addition of fault-tolerance, where the explicit knowledge of legitimate state is beneficial and where it is not very crucial.
Year
DOI
Venue
2015
10.1007/s00446-014-0227-2
Distributed Computing
Keywords
Field
DocType
Model repair,Program synthesis,Fault-tolerance,Automated formal methods
Program synthesis,Computer science,Explicit knowledge,Petroleum engineering,Theoretical computer science,Fault tolerance,Artificial intelligence,Spite
Journal
Volume
Issue
ISSN
28
3
0178-2770
Citations 
PageRank 
References 
0
0.34
37
Authors
4
Name
Order
Citations
PageRank
Fuad Abujarad1569.21
Yi-Yan Lin2213.07
Borzoo Bonakdarpour349045.02
Sandeep S. Kulkarni486379.94