Dependability analysis of fault-tolerant systems: a new look at combinatorial modeling
S.A. Doyle, J.B. Dugan · 1995
Reliable computer systems use component redundancy to achieve fault The reliability of a fault tolerant system is frequently estimated from an analytical model of the system. Two popular modeling techniques are combinatorial models and Markov models. Markov models are more comprehensive and flexible than combinatorial models, but combinatorial models can express the failure modes of a system in a more concise and understandable manner than Markov models. Combinatorial models are well understood and have the support of a rich body of research, but are inherently unable to model the dynamic system behavior associated with fault tolerant computer systems. An example of dynamic behavior that cannot be captured in a combinatorial model is the ability of a fault tolerant system to automatically recover from the occurrence of a fault during system operation. Including the concept of coverage (and the possibility that recovery may be imperfect) in the system level model is critical to an accurate dependability assessment. We develop two new algorithms for incorporating coverage into the reliability analysis of a system. In the first algorithm, we show that standard combinatorial (cutset-based) solution techniques can be used to solve a problem that was previously thought to require a Markov solution. In the second algorithm, an alternative to the traditional cutset-based solution approach to combinatorial models, the binary decision diagram (BDD), is used. Through the second approach, the time required to solve some systems is significantly reduced. It is also possible that large systems can be evaluated which could not be analyzed previously. Several applications are modeled to demonstrate the ability of the algorithms. These systems range in size and in functionality, but all have some level of fault tolerant design. Some of the systems had only been modeled with a Markov chain prior to the development of our algorithms. Another had never been buccessfully modeled at all. Another area of study which is not typically addressed is the integrated analysis of systems. Looking at only the hardware or software of a system only gives part of the picture. It is difficult to draw a clear line distinguishing the effects of hardware from those of software. To perform an accurate analysis on an integrated system, the analysis itself should be integrated. We demonstrate a new approach for performing such an analysis which combines the attributes of both Markov models and combinatorial models for the evaluation of hardware and software fault tolerance.