Conventional and Improved Inclusion-Exclusion Derivations of Symbolic Expressions for the Reliability of a Multi-State Network
Asian Journal of Research in Computer Science,
This paper deals with an emergent variant of the classical problem of computing the probability of the union of n events, or equivalently the expectation of the disjunction (ORing) of n indicator variables for these events, i.e., the probability of this disjunction being equal to one. The variant considered herein deals with multi-valued variables, in which the required probability stands for the reliability of a multi-state delivery network (MSDN), whose binary system success is a two-valued function expressed in terms of multi-valued component successes. The paper discusses a simple method for handling the afore-mentioned problem in terms of a standard example MSDN, whose success is known in minimal form as the disjunction of prime implicants or minimal paths of the pertinent network. This method utilizes the multi-state inclusion-exclusion (MS-IE) principle associated with a multi-state generalization of the idempotency property of the ANDing operation. The method discussed is illustrated with a detailed symbolic example of a real-case study, and it produces a more precise version of the same numerical value that was obtained earlier. The example demonstrates the notorious shortcomings and the extreme inefficiency that the MS-IE method suffers, but, on the positive side, it reveals the way to alternative methods, in which such a shortcoming is (partially) mitigated. A prominent and well known example of these methods is the construction of a multi-state probability-ready expression (MS-PRE). Another candidate method would be to apply the MS-IE principle to the union of fewer (factored or composite) paths that is converted (at minimal cost) to PRE form. A third candidate method, employed herein, is a novel method for combining the MS-PRE and MS-IE concepts together. It confines the use of MS-PRE to ‘shellable’ disjointing of ORed terms, and then applies MS-IE to the resulting partially orthogonalized disjunctive form. This new method makes the most of both MS-PRE and MS-IE, and bypasses the troubles caused by either of them. The method is illustrated successfully in terms of the same real-case problem used with the conventional MS-IE.
- Network reliability
- probability-ready expression
- multi-state system
- symbolic expression
- multi-state delivery network
How to Cite
Rushdi AM, Al-Khateeb DL. A review of methods for system reliability analysis: A Karnaugh-map perspective, Proceedings of the First Saudi Engineering Conference, Jeddah, Saudi Arabia. 1983;1:57- 95.
O'Connor L. The inclusion-exclusion principle and its applications to cryptography. Cryptologia. 1993;17(1):63-79.
Kahn J, Linial N, Samorodnitsky A. Inclusion-exclusion: Exact and approximate. Combinatorica. 1996;16(4):465-477.
Dohmen K. Inclusion-exclusion and network reliability. the Electronic Journal of Combinatorics. 1998;Research paper#36,5(1):1-8.
Dohmen K. An improvement of the inclusion-exclusion principle. Archiv der Mathematik. 1999;72(4):298-303.
Dohmen KL. Inclusion-exclusion: Which terms cancel?. Archiv der Mathematik. 2000;74(4):314-316.
Dohmen K. Improved inclusion-exclusion identities and Bonferroni inequalities with reliability applications. SIAM Journal on Discrete Mathematics. 2002;16(1):156-171.
Cerasoli M, Fedullo A. The inclusion-exclusion principle. Journal of Interdisciplinary Mathematics. 2002;5(2):127-141.
Kessler D, Schiff J. Inclusion-exclusion redux. Electronic Communications in Probability. 2002;7:85-96.
Calders T, Goethals B. Quick inclusion-exclusion. In International Workshop on Knowledge Discovery in Inductive Databases. Springer, Berlin, Heidelberg. 2005;86-103.
Yeh WC. A greedy branch-and-bound inclusion-exclusion algorithm for calculating the exact multi-state network reliability. IEEE Transactions on Reliability. 2008;57(1):88-93.
Rota GC. On the foundations of combinatorial theory. In Classic Papers in Combinatorics. Birkhäuser Boston. 2009;332-360.
Benaddy M, Wakrim M. Cutset enumerating and network reliability computing by a new recursive algorithm and inclusion exclusion principle. International Journal of Computer Applications. 2012;45(16):22-25.
Chen SG. Reduced recursive inclusion-exclusion principle for the probability of union events. In 2014 IEEE international conference on industrial engineering and engineering management. 2014;11-13.
Boros E, Scozzari A, Tardella F, Veneziani P. Polynomially computable bounds for the probability of the union of events. Mathematics of Operations Research. 2014;39(4):1311-1329.
Rushdi AM, Al-Qwasmi MA. Exposition and comparison of two kinds of a posteriori analysis of fault trees. Journal of King Abdulaziz University: Computing and Information Technology Sciences. 2016;5(1-2):55-74.
Yoda K, Prékopa A. Improved bounds on the probability of the union of events some of whose intersections are empty. Operations Research Letters. 2016;44(1):39-43.
Schäfer L, Garcia S, Srithammavanh V. Simplification of inclusion–exclusion on intersections of unions with application to network systems reliability. Reliability Engineering & System Safety. 2018;173:23-33.
Hao Z, Yeh WC, Wang J, Wang GG, Sun B. A quick inclusion-exclusion technique. Information Sciences. 2019;486:20-30.
Zuo MJ, Tian Z, Huang HZ. An efficient method for reliability evaluation of multistate networks given all minimal path vectors. IIE transactions. 2007;39(8):811-817.
Lin YK, Huang CF, Yeh CT. Network reliability with deteriorating product and production capacity through a multi-state delivery network, International Journal of Production Research. 2014;52(22):6681-6694.
Rushdi AMA, Al-Amoudi MA. Switching-algebraic analysis of multi-state system reliability, Journal of Engineering Research and Reports. 2018;3(3):1-22.
Rushdi AMA. Utilization of symmetric switching functions in the symbolic reliability analysis of multi-state k-out-of-n systems, International Journal of Mathematical, Engineering and Management Science. 2019;4(2):306-326.
Rushdi AMA, Al-Amoudi MA. Reliability analysis of a multi-state system using multi-valued logic, IOSR Journal of Electronics and Communication Engineering, 2019;14(1):1-10.
Rushdi AMA, Alsayegh AB. Reliability analysis of a commodity-supply multi-state system using the map method, Journal of Advances in Mathematics and Computer Science. 2019;31(2):1-17.
Rushdi AM, Ghaleb FA. Boolean-based symbolic analysis for the reliability of coherent multi-state systems of heterogeneous components. Journal of King Abdulaziz University: Computing and Information Technology Sciences. 2020;9(2):1-25.
Rushdi AM, AlHuthali SA, AlZahrani NA, Alsayegh AB. Reliability analysis of binary-imaged generalized multi-state k-out-of-n systems. International Journal of Computer Science and Network Security (IJCSNS). 2020;20(9):251-264.
Rushdi AMA, Ghaleb FAM. Reliability characterization of binary-imaged multi-state coherent threshold systems. International Journal of Mathematical, Engineering and Management Sciences. 2021;6(1):309-321.
Rushdi AMA, Amashah MH. Symbolic derivation of a probability-ready expression for the reliability analysis of a multi-state delivery network. Journal of Advances in Mathematics and Computer Science. 2021;36(2):37-56.
Rushdi AMA, Amashah MH. Symbolic reliability analysis of a multi-state network. Proceedings of the IEEE Fourth National Computing Colleges Conference (4th NCCC), Taif, Kingdom of Saudi Arabia. 2021;1-6.
Heidtmann KD. Improved method of inclusion-exclusion applied to k-out-of-n systems. IEEE Transactions on Reliability. 1982;31(1):36-40.
Rushdi AM. Reliability of k-out-of-n systems. chapter 5 in KB. Misra, new trends in system reliability evaluation, fundamental studies in engineering, Elsevier science publishers, Amsterdam, The Netherlands. 1993;16:185-227.
Sun YR, Zhou WY. An inclusion-exclusion algorithm for network reliability with minimal cut sets. American Journal of Computational Mathematics. 2012;2(4):316-320.
Goaoc X, Matoušek J, Paták P, Safernová Z, Tancer M. Simplifying inclusion–exclusion formulas. Combinatorics, Probability and Computing. 2015;24(2):438-456.
Rushdi AM, Hassan AK. An exposition of system reliability analysis with an ecological perspective. Ecological Indicators. 2016;63:282-295.
Hall M. Combinatorial theory. Blaisdell publishing company, Waltham, MA, USA; 1967.
Feller W. An introduction to probability theory and its applications. Third Edition, Wiley; 1968;1.
Trivedi KS. Probability and statistics with reliability, queuing, and computer science applications. Englewood cliffs: NJ: Prentice-Hall; 1982.
Rushdi AM. Utilization of symmetric switching functions in the computation of k-out-of-n system reliability. Microelectronics and Reliability. 1986;26(5):973-987.
Rushdi AM, Alsulami AE. Cost elasticities of reliability and MTTF for k-out-of-n systems, Journal of Mathematics and Statistics. 2007;3(3):122-128.
Rushdi AM. Partially-redundant systems: Examples, reliability, and life expectancy, Int. Mag. Adv. Comput. Sci. Telecommun. 2010;1(1):1–13.
Rushdi AM, Rushdi MA. Switching-algebraic analysis of system reliability, Chapter 6 in M. Ram and P. Davim (Editors), Advances in Reliability and System Engineering. Springer International Publishing, Cham, Switzerland. 2017;139-161.
Rushdi RA, Rushdi AM. Karnaugh-map utility in medical studies: The case of Fetal Malnutrition. International Journal of Mathematical, Engineering and Management Sciences. 2018;3(3):220-244.
Rushdi, RA, Rushdi AM. Common fallacies of probability in medical context: A simple mathematical exposition. Journal of Advances in Medicine and Medical Research. 2018;26(1):1-21.
Rushdi RAM, Rushdi AMA. Mathematics and examples for avoiding common probability fallacies in medical disciplines. Chapter 11 in Current Trends in Medicine and Medical Research, Book Publishers International, Hooghly, West Bengal, India, 2019;1:106-132.
Rushdi AM, Serag HA. Solutions of ternary problems of conditional probability with applications to mathematical epidemiology and the COVID-19 pandemic. International Journal of Mathematical, Engineering and Management Sciences. 2020;5(5):787-811.
Rushdi AM, Goda AS. Symbolic reliability analysis via Shannon's expansion and statistical independence, Microelectronics and Reliability. 1985;25(6):1041-1053.
Rushdi AM, Abdul Ghani AA. A comparison between reliability analyses based primarily on disjointness or statistical independence: The case of the generalized INDRA network, Microelectronics and Reliability. 1993;33(7):965-978.
Rushdi AM, Ba-Rukab OM. Fault-tree modelling of computer system security. International Journal of Computer Mathematics. 2005;82(7):805-819.
Rushdi AM, Hassan AK. Reliability of migration between habitat patches with heterogeneous ecological corridors. Ecological Modelling. 2015;304:1-10.
Bamasak SM, Rushdi AM. Uncertainty analysis of fault-tree models for power system protection. Journal of Qassim University: Engineering and Computer Sciences. 2016;8(1):65-80.
Rushdi MAM, Ba-Rukab OM, Rushdi AM. Multi-dimensional recursion relations and mathematical induction techniques: The case of failure frequency of k-out-of-n systems J. King Abdulaziz University: Engineering Sciences. 2016;27(2):15–31.
Rushdi AM, Alturki AM. Novel representations for a coherent threshold reliability system: A tale of eight signal flow graphs. Turkish Journal of Electrical Engineering & Computer Sciences. 2018;26(1):257-269.
Rushdi AM, Alturki AM. Unification of mathematical concepts and algorithms of k-out-of-n system reliability: A perspective of improved disjoint products. Journal of Engineering Research. 2018;6(4):1-31.
Rushdi AMA, Hassan AK, Moinuddin M. System reliability analysis of small-cell deployment in heterogeneous cellular networks, Telecommunication Systems. 2019;73:371-381.
Rushdi AM, Hassan AK. On the interplay between ecology and reliability. In Misra, KB (Editor), Handbook of Advanced Performability Engineering, Springer, Cham, Switzerland. 2021;785-809).
Ball MO, Provan JS. Disjoint products and efficient computation of reliability. Operations Research. 1988;36(5):703-15.
Boros E, Crama Y, Ekin O, Hammer PL, Ibaraki T, Kogan A. Boolean normal forms, shellability, and reliability computations. SIAM Journal on Discrete Mathematics. 2000;13(2):212-226.
Bruni R. On the orthogonalization of arbitrary Boolean formulae. Journal of Applied Mathematics and Decision Sciences. 2005;2005(2):61-74.
Rushdi AM, Alturki AM. Reliability of coherent threshold systems. Journal of Applied Sciences. 2015;15(3):431-443.
Rushdi AMA, Amashah MH. A liaison among inclusion-exclusion, probability-ready expressions and Boole-Shannon expansion for multi-state reliability. Journal of King Abdulaziz University: Computing and Information Technology Sciences. 2021;10(2).
Rushdi AM. Map derivation of the minimal sum of a switching function from that of its complement. Microelectronics and Reliability. 1985;25(6):1055-1065.
Liu HH, Yang WT, Liu CC. An improved minimizing algorithm for the summation of disjoint products by Shannon's expansion. Microelectronics and Reliability. 1993;33(4):599-613.
Chang YR, Amari SV, Kuo SY. Reliability evaluation of multi-state systems subject to imperfect coverage using OBDD. In 2002 Pacific Rim International Symposium on Dependable Computing, 2002. Proceedings. 2002;193-200. IEEE.
Ghosh S, Bhunia S, Roy K. Shannon expansion based supply-gated logic for improved power and testability. In 14th Asian Test Symposium (ATS'05). 2005;404-409. IEEE.
Shrestha A, Xing L, Dai Y. Decision diagram based methods and complexity analysis for multi-state systems. IEEE Transactions on Reliability. 2009;59(1):145-161.
Amari SV, Xing L, Shrestha A, Akers J, Trivedi KS. Performability analysis of multistate computing systems using multivalued decision diagrams. IEEE Transactions on Computers. 2010;59(10):1419-1433.
Abstract View: 44 times
PDF Download: 25 times