Fundamental Reliability Theory

This chapter covers basic probability concepts, reliability measures, fault tree (FT) modeling, binary decision diagrams (BDDs), and Markov processes. Based on the types of logic gates and events used for constructing the FT model, FT can be classified as static, dynamic, phased-mission, and multi-state FTs. To construct a reduced ordered BDD from an FT, each input variable encoding the binary state of a system component is assigned a different index or order first. The chapter presents basics of BDDs and how to construct and evaluate a BDD model for system reliability analysis. It describes several quantitative reliability measures for a nonrepairable unit, including the failure function, reliability function, failure rate function, mean time to failure, and mean residual life. The state space-based methods belong to the analytical methods for system reliability analysis. Various reliability analysis software tools have been developed.

References

Allen, A. (1990). Probability, Statistics and Queuing Theory: with Computer Science Applications, 2e. Academic Press.
Google Scholar
Watson, H.A. (1961). Launch Control Safety Study. Murray Hill, NJ: Bell Telephone Laboratories.
Google Scholar
Vesely, W.E., Goldberg, F.F., Roberts, N.H., and Haasl, D.F. (1981). Fault Tree Handbook. Washington, DC: U.S. Nuclear Regulatory Commission.
Google Scholar
Dugan, J.B. and Doyle, S.A. (1996). New results in fault-tree analysis. In: Tutorial Notes of Annual Reliability and Maintainability Symposium, Las Vegas, NV, USA.
Google Scholar
Ke, J., Su, Z., Wang, K., and Hsu, Y. (2010). Simulation inferences for an availability system with general repair distribution and imperfect fault coverage. Simulation Modelling Practice and Theory 18 (3): 338–347.
10.1016/j.simpat.2009.12.001
Web of Science® Google Scholar
Bobbio, A., Franceschinis, G., Gaeta, R., and Portinale, L. (1999). Exploiting petri nets to support fault tree based dependability analysis. In: Proceedings of the 8th International Workshop on Petri Nets and Performance Models, 146–155.
Google Scholar
Dugan, J.B., Bavuso, S.J., and Boyd, M.A. (1993). Fault trees and Markov models for reliability analysis of fault tolerant systems. Reliability Engineering & System Safety 39: 291–307.
10.1016/0951-8320(93)90005-J
Web of Science® Google Scholar
Hura, G.S. and Atwood, J.W. (1988). The use of petri nets to analyze coherent fault trees. IEEE Transactions on Reliability 37 (5): 469–474.
10.1109/24.9864
Web of Science® Google Scholar
Malhotra, M. and Trivedi, K.S. (1995). Dependability modeling using petri nets. IEEE Transactions on Reliability 44 (3): 428–440.
10.1109/24.406578
Web of Science® Google Scholar
Rauzy, A. (1993). New algorithms for fault tree analysis. Reliability Engineering & System Safety 40: 203–211.
10.1016/0951-8320(93)90060-C
Web of Science® Google Scholar
Coudert, O. and Madre, J.C. (1993). Fault tree analysis: 10²⁰ prime implicants and beyond. In: Proceedings of Annual Reliability and Maintainability Symposium . Atlanta, GA, USA.
Google Scholar
Sinnamon, R. and Andrews, J.D. (1996). Fault tree analysis and binary decision diagrams. In: Proceedings of the Annual Reliability and Maintainability Symposium. Las Vegas, NV, USA.
Google Scholar
Gulati, R. and Dugan, J.B. (1997). A modular approach for analyzing static and dynamic fault trees. In: Proceedings of the Annual Reliability and Maintainability Symposium . Philadelphia, PA, USA.
Google Scholar
Sahner, R., Trivedi, K.S., and Puliafito, A. (1996). Performance and Reliability Analysis of Computer Systems: An Example-Based Approach Using the SHARPE Software Package. Kluwer Academic Publisher.
10.1007/978-1-4615-2367-3
Web of Science® Google Scholar
Xing, L. and Amari, S.V. (2008). Fault tree analysis. In: Handbook of Performability Engineering. Springer-Verlag.
10.1007/978-1-84800-131-2_38
Google Scholar
Xing, L. (2007). Reliability importance analysis of generalized phased-mission systems. International Journal of Performability Engineering 3 (3): 303–318.
Google Scholar
Astapenko, D. and Bartlett, L.M. (2009). Phased mission system design optimisation using genetic algorithms. International Journal of Performability Engineering 5 (4): 313–324.
Google Scholar
Dai, Y., Levitin, G., and Xing, L. (2014). Structure optimization of non-repairable phased mission systems. IEEE Transactions on Systems, Man, and Cybernetics: Systems 44 (1): 121–129.
Google Scholar
Alam, M., Min, S., Hester, S.L., and Seliga, T.A. (2006). Reliability analysis of phased-mission systems: a practical approach. In: Proceedings of Annual Reliability and Maintainability Symposium . Newport Beach, CA. USA.
Google Scholar
Murphy, K.E., Carter, C.M., and Malerich, A.W. (2007). Reliability analysis of phased-mission systems: a correct approach. In: Proceedings of Annual Reliability and Maintainability Symposium . Orlando, FL.
Google Scholar
Dugan, J.B. (1991). Automated analysis of phased-mission reliability. IEEE Transactions on Reliability 40 (1): 45–52,55.
10.1109/24.75332
Web of Science® Google Scholar
Smotherman, M.K. and Zemoudeh, K. (1989). A non-homogeneous Markov model for phased-mission reliability analysis. IEEE Transactions on Reliability 38 (5): 585–590.
10.1109/24.46486
Web of Science® Google Scholar
Mura, I. and Bondavalli, A. (2001). Markov regenerative stochastic petri nets to model and evaluate phased mission systems dependability. IEEE Transactions on Computers 50 (12): 1337–1351.
10.1109/TC.2001.970572
Web of Science® Google Scholar
Esary, J.D. and Ziehms, H. (1975). Reliability analysis of phased missions. In: Reliability and fault tree analysis: theoretical and applied aspects of system reliability and safety assessment, 213–236. Philadelphia, PA: SIAM.
Google Scholar
Somani, A.K. and Trivedi, K.S. (1997). Boolean algebraic methods for phased-mission system analysis. Technical Report NAS1–19480. NASA Langley Research Center, Hampton, Virginia, USA.
Google Scholar
Xing, L. and Dugan, J.B. (2002). Analysis of generalized phased mission system reliability, performance and sensitivity. IEEE Transactions on Reliability 51 (2): 199–211.
10.1109/TR.2002.1011526
Web of Science® Google Scholar
Xing, L. and Levitin, G. (2011). Combinatorial algorithm for reliability analysis of multi-state systems with propagated failures and failure isolation effect. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans 41 (6): 1156–1165.
10.1109/TSMCA.2011.2116002
Google Scholar
Shrestha, A., Xing, L., and Dai, Y.S. (2011). Reliability analysis of multi-state phased-mission systems with unordered and ordered states. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans 41 (4): 625–636.
Google Scholar
Levitin, G. and Xing, L. (2010). Reliability and performance of multi-state systems with propagated failures having selective effect. Reliability Engineering & System Safety 95 (6): 655–661.
10.1016/j.ress.2010.02.003
Web of Science® Google Scholar
Huang, J. and Zuo, M.J. (2004). Dominant multi-state systems. IEEE Transactions on Reliability 53 (3): 362–368.
10.1109/TR.2004.833311
Web of Science® Google Scholar
Levitin, G. (2003). Reliability of multi-state systems with two failure-modes. IEEE Transactions on Reliability 52 (3): 340–348.
10.1109/TR.2003.818714
Google Scholar
Chang, Y.-R., Amari, S.V., and Kuo, S.-Y. (2005). OBDD-based evaluation of reliability and importance measures for multistate systems subject to imperfect fault coverage. IEEE Transactions on Dependable and Secure Computing 2 (4): 336–347.
Google Scholar
Li, W. and Pham, H. (2005). Reliability modeling of multi-state degraded systems with multi-competing failures and random shocks. IEEE Transactions on Reliability 54: 297–303.
10.1109/TR.2005.847278
PubMed Web of Science® Google Scholar
Zang, X., Wang, D., Sun, H., and Trivedi, K.S. (2003). A BDD-based algorithm for analysis of multistate systems with multistate components. IEEE Transactions on Computers 52 (12): 1608–1618.
10.1109/TC.2003.1252856
Web of Science® Google Scholar
Amari, S.V., Xing, L., Shrestha, A. et al. (2010). Performability analysis of multi-state computing systems using multi-valued decision diagrams. IEEE Transactions on Computers 59 (10): 1419–1433.
Google Scholar
Lee, C.Y. (1959). Representation of switching circuits by binary-decision programs. Bell Systems Technical Journal 38: 985–999.
10.1002/j.1538-7305.1959.tb01585.x
Web of Science® Google Scholar
Bryant, R.E. (1986). Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers 35 (8): 677–691.
10.1109/TC.1986.1676819
Web of Science® Google Scholar
Miller, D.M. (1993). Multiple-valued logic design tools. In: Proceedings of 23rd International Symposium on Multiple-Valued Logic (ISMVL), 2–11. Sacramento, CA, USA.
Google Scholar
Miller, D.M. and Drechsler, R. (1998). Implementing a multiple-valued decision diagram package. In: Proceedings of 23rd International Symposium on Multiple-Valued Logic (ISMVL), 52–57. Fukuoka, Japan.
Google Scholar
Burch, J.R., Clarke, E.M., Long, D.E. et al. (1994). Symbolic model checking for sequential circuit verification. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 13 (4): 401–424.
10.1109/43.275352
Web of Science® Google Scholar
Ciardo, G. and Siminiceanu, R. (2001). Saturation: an efficient iteration strategy for symbolic state space generation. In: Tools and Algorithms for the Construction and Analysis of Systems, 328–342.
Google Scholar
Hermanns, H., Meyer-Kayser, J., and Siegle, M. (1999). Multi terminal binary decision diagrams to represent and analyse continuous time Markov chains. In: Numerical Solution of Markov Chains, 188–207.
Google Scholar
Miner, A.S. and Cheng, S. (2004). Improving efficiency of implicit Markov chain state classification. In: Proceedings of First International Conference on the Quantitative Evaluation of Systems (QEST ‘04), 262–271. Enschede, The Netherlands.
Google Scholar
Ciardo, G. (2004). Reachability set generation for petri nets: can brute force be smart. In: Proceedings of 25th International Conference on the Applications and Theory of Petri Nets (ICATPN ‘04), 17–34.
Google Scholar
Miner, A.S. and Ciardo, G. (1999). Efficient reachability set generation and storage using decision diagrams. In: Application and Theory of Petri Nets, 6–25.
10.1007/3-540-48745-X_2
Google Scholar
Burch, J.R., Clarke, E.M., McMillan, K.L. et al. (1990). Symbolic model checking: 10²⁰ states and beyond. In: Proceedings of Fifth Annual IEEE Symposium on the Logic in Computer Science (LICS’ 90), 1–33. Philadelphia, PA, USA.
Google Scholar
Chechik, M., Gurfinkel, A., Devereux, B. et al. (2006). Data structures for symbolic multi-valued model-checking. Formal Methods in System Design 29 (3): 295–344.
Google Scholar
Corsini, M.-M. and Rauzy, A. (1994). Symbolic model checking and constraint logic programming: a cross-fertilization. In: Proceedings of Fifth European Symp. Programming (ESOP'94), 180–194.
Google Scholar
Xing, L. and Amari, S.V. (2015). Binary Decision Diagrams and Extensions for System Reliability Analysis. Salem, MA: Wiley-Scrivener.
10.1002/9781119178026
Google Scholar
Minato, S., Ishiura, N., and Yajima, S. (1990). Shared binary decision diagrams with attributed edges for efficient Boolean function manipulation. In: Proceedings of the 27th ACM/IEEE Design Automation Conference, 52–57. Orlando, FL, USA.
Google Scholar
Fujita, M., Fujisawa, H., and Kawato, N. (1988). Evaluation and improvements of Boolean comparison method based on binary decision diagrams. In: Proceedings of IEEE International Conference on Computer Aided Design, 2–5. Santa Clara, CA, USA.
Google Scholar
Fujita, M., Fujisawa, H., and Matsugana, Y. (1993). Variable ordering algorithm for ordered binary decision diagrams and their evaluation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 12 (1): 6–12.
Google Scholar
Bouissou, M., Bruyere, F., and Rauzy, A. (1997). BDD based fault-tree processing: a comparison of variable ordering heuristics. In: Proceedings of ESREL Conference , Lisbon, Portugal.
Google Scholar
Bouissou, M. (1996). An ordering heuristics for building binary decision diagrams from fault-trees. In: Proceedings of the Annual Reliability and Maintainability Symposium . Las Vegas, NV, USA.
Google Scholar
Butler, K.M., Ross, D.E., Kapur, R., and Mercer, M.R. (1991). Heuristics to compute variable orderings for efficient manipulation of ordered BDDs. In: Proceedings of the 28th Design Automation Conference . San Francisco, CA, USA.
Google Scholar
Gulati, R. (1996). A modular approach to static and dynamic fault tree analysis. M. S. Thesis, Electrical Engineering, University of Virginia.
Google Scholar
Sune, V. and Carrasco, J.A. (1997). A method for the computation of reliability bounds for non-repairable fault-tolerant systems. In: Proceedings of the 5th IEEE International Symposium on Modeling, Analysis, and Simulation of Computers and Telecommunication System, 221–228. Haifa, Israel.
Google Scholar
Sune, V. and Carrasco, J.A. (2001). A failure-distance based method to bound the reliability of non-repairable fault-tolerant systems without the knowledge of minimal cutsets. IEEE Transactions on Reliability 50 (1): 60–74.
Google Scholar
Manian, R., Dugan, J.B., Coppit, D., and Sullivan, K.J. (1998). Combining various solution techniques for dynamic fault tree analysis of computer systems. In: Proceedings of the 3rd IEEE International High-Assurance Systems Engineering Symposium, 21–28. Washington, DC, USA.
Google Scholar
Dutuit, Y. and Rauzy, A. (1996). A linear time algorithm to find modules of fault trees. IEEE Transactions on Reliability 45 (3): 422–425.
10.1109/24.537011
Web of Science® Google Scholar
Sullivan, K.J., Dugan, J.B., and Coppit, D. (1999). The Galileo fault tree analysis tool. In: Proceedings of the 29th International Symposium on Fault-Tolerant Computing . Madison, WI, USA.
Google Scholar
FaultTree+, https://www.isograph.com/software/reliability-workbench/fault-tree-analysis-software, accessed in March 2018.
Google Scholar
BlockSim, https://www.reliasoft.com/products/reliability-analysis/blocksim, accessed in March 2018.
Google Scholar

Dynamic System Reliability: Modeling and Analysis of Dynamic and Dependent Behaviors