OBDD-Based Evaluation of Reliability and Importance Measures for Multistate Systems Subject to Imperfect Fault Coverage
|
Algorithms for evaluating the reliability of a complex system such as a multistate fault-tolerant computer system have become more important recently. They are designed to obtain the complete results quickly and accurately even when there exist a number of dependencies such as shared loads (reconfiguration), degradation, and common-cause failures. This paper presents an efficient method based on Ordered Binary Decision Diagram (OBDD) for evaluating the multistate system reliability and the Griffith's importance measures which can be regarded as the importance of a system-component state of a multistate system subject to imperfect fault-coverage with various performance requirements. This method combined with the conditional probability methods can handle the dependencies among the combinatorial performance requirements of system modules and find solutions for multistate imperfect coverage model. The main advantage of the method is that its time complexity is equivalent to that of the methods for perfect coverage model and it is very helpful for the optimal design of a multistate fault-tolerant system.
[1] 336 J.D. Murchland, “Fundamental Concepts and Relations for Reliability Analysis of Multistate Systems,” Reliability and Fault Tree Analysis, Theoretical, and Applied Aspects of System Reliability (SIAM), pp. 581-618, 1975.
[2] A.P. Wood, “Multistate Block Diagrams and Fault Trees,” IEEE Trans. Reliability, vol. 34, no. 3, pp. 236-240, Aug. 1985.
[3] S. Garribba, E. Guagnini, and P. Mussio, “Multiple-Valued Logic Trees: Meaning and Prime Implicants,” IEEE Trans. Reliability, vol. 34, no. 5, pp. 463-472, Dec. 1985.
[4] A. Gandini, “Importance and Sensitivity Analysis in Assessing System Reliability,” IEEE Trans. Reliability, vol. 39, no. 1, pp. 61-69, Apr. 1990.
[5] J. Xue, “On Multistate System Analysis,” IEEE Trans. Reliability, vol. 34, no. 4, pp. 329-337, Oct. 1985.
[6] J. Xue and K. Yang, “Dynamic Reliability Analysis of Coherent Multistate Systems,” IEEE Trans. Reliability, vol. 44, pp. 683-688, Dec. 1995.
[7] G. Levitin, “Incorporating Common-Cause Failure into Nonrepairable Multistate Series-Parallel System Analysis,” IEEE Trans. Reliability, vol. 50, pp. 380-388, Dec. 2001.
[8] J.B. Dugan, “Fault Tree and Imperfect Coverage,” IEEE Trans. Reliability, vol. 38, pp. 177-185, June 1989.
[9] S.V. Amari, J.B. Dugan, and R.B. Misra, “Optimal Reliability of Systems Subject to Imperfect Fault-Coverage,” IEEE Trans. Reliability, vol. 48, pp. 275-284, Sept. 1999.
[10] A. Reibman and K.S. Trivedi, “Numerical Transient Analysis of Markov Models,” Computers and Operations Research, vol. 15, no. 1, pp. 19-36, 1998.
[11] K.S. Trivedi, Probability and Statistics with Reliability, Queuing, and Computer Science Applications. Prentice-Hall, 1982.
[12] R.E. Bryant, “Graph-Based Algorithms for Boolean Function Manipulation,” IEEE Trans. Computers, vol. 35, no. 8, pp. 677-691, Aug. 1986.
[13] Y.R. Chang, S.V. Amari, and S.Y. Kuo, “Computing System Failure Frequencies and Reliability Importance Measure Using OBDD,” IEEE Trans. Computers, vol. 53, no. 1, pp. 54-68, Jan. 2004.
[14] Y.R. Chang, S.V. Amari, and S.Y. Kuo, “Reliability Evaluation of Multi-State Systems Subject to Imperfect Coverage Using OBDD,” Proc. 2002 Pacific Rim Int'l Symp. Dependable Computing (PRDC '02), pp. 193-200, 2002.
[15] F.M. Yeh, S.K. Lu, and S.Y. Kuo, “OBDD-Based Evaluation of K-Terminal Network Reliability,” IEEE Trans. Reliability, vol. 51, no. 4, pp. 443-451, Dec. 2002.
[16] S.Y. Kuo, S.K. Lu, and F.M. Yeh, “Determining Terminal-Pair Reliability Based on Edge Expansion Diagrams Using OBDD,” IEEE Trans. Reliability, vol. 48, pp. 234-246, Sept. 1999.
[17] X. Zang, H. Sun, and K.S. Trivedi, “Dependability Analysis of Distributed Computer Sys-tems with Imperfect Coverage,” Proc. 29th Ann. Int'l Symp. Fault-Tolerant Computing (FTC-29), pp. 330-337, 1999.
[18] X. Zang, D. Wang, H. Sun, K.S. Trivedi, “A BDD-Based Algorithm for Analysis of Multistate Systems with Multistate Components,” IEEE Trans. Computers, vol. 52, no. 12, pp. 1608-1618, Dec. 2003.
[19] B. Lin, O. Coudert, and J.C. Madre, “Symbolic Prime Generation for Multiple-Valued Function,” Proc. 29th ACM/IEEE Design Automation Conf., pp. 40-44, 1992.
[20] E.A. Elsayed, Reliability Engineering. Addison Wesley Longman, 1996.
[21] A. Hoyland and M. Rausand, System Reliability Theory: Models and Statistical Methods. John Wiley & Sons, 1994.
[22] F.C. Meng, “Comparing the Importance of System Components by Some Structural Characteristics,” IEEE Trans. Reliability, vol. 45, no. 1, pp. 59-65, Mar. 1996.
[23] F.C. Meng, “Some Further Results on Ranking the Importance of System Components,” Reliability Eng. and System Safety, vol. 47, pp. 97-101, 1995.
[24] J.S. Hong and C.H. Lie, “Joint Reliability-Importance of Two Edges in an Undirected Network,” IEEE Trans. Reliability, vol. 42, no. 1, pp. 17-23, Mar. 1993.
[25] M.J. Armstrong, “Joint Reliability-Importance of Components,” IEEE Trans. Reliability, vol. 44, no. 3, pp. 408-412, Sept. 1995.
[26] R.E. Barlow and A.S. Wu, “Coherent Systems with Multistate Components,” Math. Operations Research, vol. 3, pp. 275-281, 1978.
[27] T. Aven, “On Performance Measures for Multistate Monotone Systems,” Reliability Eng. and System Safety, vol. 41, pp. 259-266, 1993.
[28] B. Natvig, “Two Suggestions of How to Define a Multistate Coherent System,” Advanced Applied Probability, vol. 14, pp. 434-457, 1982.
[29] H.W. Block, “A Decomposition for Multistate Monotone System,” J. Applied Probability, vol. 19, pp. 391-402, 1982.
[30] F.C. Meng, “Component-Relevancy and Characterization Results in Multistate Systems,” IEEE Trans. Reliability, vol. 42, no. 3, pp. 478-483, Sept. 1993.
[31] W.S. Griffith, “Multistate Reliability Models,” J. Applied Probability, vol. 17, pp. 735-744, 1980.
[32] S. Wu and L.Y. Chan, “Performance Utility-Analysis of Multistate Systems,” IEEE Trans. Reliability, vol. 52, no. 1, pp. 14-21, Mar. 2003.
[33] A. Rauzy, “New Algorithms for Fault Tree Analysis,” Reliability Eng. and System Safety, vol. 40, pp. 203-211, 1993.
[34] R.M. Sinnamon and J.D. Andrews, “Improved Efficiency in Qualitative Fault Tree Analysis,” Quality and Reliability Eng. Int'l, vol. 13, pp. 293-298, 1997.
[35] S.V. Amari, J.B. Dugan, and R.B. Misra, “A Separable Method for Incorporating Imperfect Fault-Coverage into Combinatorial Models,” IEEE Trans. Reliability, pp. 267-274, Sept. 1999.
[36] J.B. Dugan and K.S. Trivedi, “Coverage Modeling for Dependability Analysis of Fault-Coverage Systems,” IEEE Trans. Computers, vol. 38, pp. 775-787, June 1989.
[37] S.A. Doyle, J.B. Dugan, and F.A. Patterson-Hine, “A Combinatorial Approach to Modeling Imperfect Coverage,” IEEE Trans. Reliability, vol. 44, pp. 87-94, Mar. 1995.
[38] H. Sun, X. Zang, and K.S. Trivedi, “A BDD-Based Algorithm for Reliability Analysis of Phased-Mission Systems,” IEEE Trans. Reliability, vol. 48, no. 1, pp. 50-60, Mar. 1999.
[39] J.B. Dugan, S.J. Bavuso, and M.A. Boyd, “Dynamic Fault-Tree Models for Fault-Tolerant Computer Systems,” IEEE Trans. Reliability, vol. 41, no. 3, pp. 363-377, Sept. 1992.
[40] S.V. Amari and R.B. Misra, “Comment on: Dynamic Reliability Analysis of Coherent Multi-State Systems,” IEEE Trans. Reliability, vol. 46, pp. 460-461, Dec. 1997.
Index Terms:
Index Terms- Reliability, multistate system, OBDD, fault-coverage, importance measure.
Citation:
Yung-Ruei Chang, Suprasad V. Amari, Sy-Yen Kuo, "OBDD-Based Evaluation of Reliability and Importance Measures for Multistate Systems Subject to Imperfect Fault Coverage," IEEE Transactions on Dependable and Secure Computing, vol. 2, no. 4, pp. 336-347, Oct.-Dec. 2005, doi:10.1109/TDSC.2005.51
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb