Specification and Solution of Dependability Models of Fault-tolerant Systems
Manish Malhotra · 1993
The modeling and analysis methodology consists of three main phases: model specification, model generation, and model solution. We consider some specific problems in each of these areas. First, we establish a hierarchy of dependability model types according to their modeling power. Algorithms to convert one model type into another are provided. We show that fault-trees with repeated events (FTRE) are the most powerful combinatorial model type. Then we show how Petri-net based models can be used for dependability modeling. Algorithms to convert a FTRE model to equivalent generalized stochastic Petri net (GSPN) and stochastic reward net (SRN) models are presented. Our comparison reveals that SRNs permit a much more concise description of dependability models than GSPNs do. We then present a methodology for formal expression of hierarchy in model specification and solution that offers a unified view of various kinds of hierarchical modeling techniques including iterative hierarchical modeling based on fixed-point iteration, non-iterative hierarchical modeling, reward-based performability modeling, behavioral decomposition, and approximate model decomposition. Model generation consists of converting from the specification-model-type to solution-model-type. We consider the conversion of semi-Markov models to Markov models using the technique of phase approximations. We describe a complete approach to phase-approximations, including choice of phase-approximation class, estimation of the selected parameters, and implementation of the approximation approach in a modeling toolkit. We also describe a new hybrid approach for parameter estimation that combines moment-matching with least squares fitting. Model solution is the next step after model generation. We describe an approach to design efficient methods for numerical transient solution of stiff Markov chains. Our approach uses a combination of explicit and implicit ODE methods. Finally we describe an application of dependability modeling and analysis. We model and analyze dependability of disk array systems. We develop detailed models and introduce new measures to compare various RAID (Redundant Arrays of Inexpensive Disks) architectures. The coverage of disk failures is analytically computed based on the error detection and correction mechanism. Models that take into account placement strategies of support hardware are also developed.