| Dependability analysis of computer systems and communication networks becomes increasingly important as these systems are expanding into our everyday life. Reliable systems often use component redundancy to achieve higher dependability, which makes the systems more complex and larger and poses a challenge to the existing modeling techniques. In this dissertation, we propose some fast algorithms for the analysis of large dependability models, such as reliability graphs, phased-mission systems, multistate systems and distributed computer systems.; These fast analysis algorithms are based on binary decision diagrams (BDD) that were widely used in VLSI design and verification as an efficient method to manipulate Boolean expressions. By comparison with other conventional algorithms, we show that our BDD-based algorithms are more efficient in both computation time and storage space used in the analysis of large combinatorial models. Beyond that, BDDs have another attractive feature, i.e., they can deal with some kinds of dependencies between system components using special manipulations. This feature enables us to use combinatorial models to analyze some systems that were previously thought to require the use of Markov chains. Markov models are often used in the analysis of phased-mission systems and multistate systems. In this dissertation, some algorithms with greater efficiency are proposed to solve combinatorial models with dependencies between components in the analysis of phased-mission systems and multistate systems.; The use of BDDs in dependability analysis is a relatively new concept. In the previous work, BDDs were used only in the reliability analysis of fault trees. In this dissertation, we extend the use of BDDs to the other dependability models, and show that the BDD solution method is a dramatic breakthrough for the analysis of large systems. The efficiency of our BDD-based algorithms makes it possible for us to study some practical and large reliability models. |
