Unification of mathematical concepts and algorithms of k-out-of-n system reliability: A perspective of improved disjoint products
Abstract
The k-out-of-n system model is the most prominent model of coherent system reliability, with a variety of important special cases, generalizations, and extensions thereof. In particular, the k-outof- n reliabilities (1 ≤ k ≤ n) constitute a basis for expressing the reliability of an n-order coherent
system in terms of its signature (destruction spectrum). A notable algorithm for computing the reliability of a k-out-of-n system is the Improved Disjoint Products (IMDP) algorithm. This paper has four goals, namely, (a) to present a detailed and novel exposition of the IMDP algorithm; (b) to demonstrate that the IMDP algorithm is derivable from the BH-2 algorithm, which is an enhancement of the BH-1 algorithm that is used for evaluating the probability of exactly k successes among n Bernoulli trials and, hence, for computing the probability mass function (pmf) of the generalized binomial distribution; (c) to demonstrate that the IMDP algorithm can be derived from the AR algorithm, which is the Reduced-Ordered-Binary-Decision-Diagram (ROBDD) algorithm for evaluating the k-out-of-n reliability and also for computing the Cumulative Distribution
Function (CDF) of the generalized binomial distribution; and (d) to show that the IMDP algorithm is a collective orthogonalization (disjointness) algorithm for a shellable sum-of-products formula (DNF) for k-out-of-n success. The paper plays a unifying role for a variety of concepts and algorithms and tries to emphasize similarities and interrelations among them, while pinpointing any subtle differences among them. A common denominator in explaining the various algorithms is the use of signal flow graphs that are compact, regular, and acyclic. For these loopless graphs, the gain formula requires only simple path enumeration, as well as a calculation of the transmittances of the paths.
References
Abraham, J. A. 1979. An improved algorithm for network reliability, IEEE Transactions on Reliability,
R-28(1): 58–61.
Agrawal, A. & Barlow, R. E. 1984. A survey of network reliability and domination theory. Operations Research,
(3): 478–492.
Akers, S. 1960. Binary decision diagrams, IEEE Transaction on Computers, C-27(6): 509–516.
Al-Qasimi, A.M. &. Rushdi, A.M. 2008. A tutorial on how to efficiently calculate and format tables of the
Binomial Distribution. Journal of King Abdulaziz University: Engineering Sciences, 19(1): 3–17.
Alturki, A. M. & Rushdi, A. M. 2016. Weighted voting systems: A threshold-Boolean perspective, Journal
of Engineering Research. 4(1): 125–143.
Amari, S. V. & Bergman, R. 2008. Reliability analysis of k-out-of-n load-sharing systems. In the Annual
IEEE Reliability and Maintainability Symposium, 2008 (RAMS 2008): 440–445.
Amari V., Misra B. Krishna & Pham Hoang. 2008. Tampered failure rate load-sharing systems: status and
perspectives. Handbook of performability engineering. Springer London,. 291–308.
Amari, S. V., Zuo, M. J. & Dill, G. 2008. O(kn) Algorithms for Analyzing Repairable and Non-Repairable
k-out-of-n: G Systems. Chapter 21 in: Handbook of Performability Engineering, Misra, K.B. (Editpor).
Springer, London, UK: 309–320.
Ball, M. O. & Provan, J. S. 1988. Disjoint products and efficient computation of reliability, Operations
Research, 36(5): 703–715.
Bamasak, S. M. & Rushdi, A. M. 2016. Uncertainty analysis of fault-tree models for power system protection.
Journal of Qassim University: Engineering and Computer Sciences, 8(1): 65–80.
Barlow, R. E. & Heidtmann, K. D. 1984. Comments and reply on ‘Computing k-out-of-n system reliability’,
IEEE Transactions on Reliability, R-33(4): 322–323.
Barlow, R. E. & Iyer, S. 1988. Computational complexity of coherent systems and the reliability polynomial.
Probability in the Engineering and Informational Sciences, 2(4): 461–469.
Barlow, R. E. & Proschan, F. 1996. Mathematical Theory of Reliability, SIAM, New York, NY, USA.
Belfore, II, L. A. 1995. An O(n(log2n)2) Algorithm for Computing the Reliability of k-out-of-n:G & k-to-
-out-of-n:G Systems, IEEE Transactions on Reliability, 44(1): 132–136.
Bergman, B. 1985. On reliability theory and its applications (with discussion), Scandinavian Journal of
Statistics, 12(1): 1–41.
Birnbaum, Z. W., Esary, J. D. & Saunders, S. 1961. Multi-Component systems and structures and their
reliability, Technometrics, 3(1): 55–77.
Bjorkman k. 2013. Solving dynamic flow graph methodology models using binary decision diagrams. Reliability
Engineering & System Safety; 111:206–16.
Boland, P. J. 2001. Signatures of indirect majority systems, Journal of Applied Probability, 38: 597–603.
Boland, P. J. & Samaniego, F. J. 2004a. The Signature of a Coherent System and its Applications in Reliability.
In: Soyer, R., Mazzuchi, T. A., Singpurwalla, N. D. (Editors) Mathematical Reliability: An Expository
Perspective, pp. 3-30, Kluwer Academic Publishers, Boston, MA, USA.
Boland, P. J. & Samaniego, F. J. 2004b. Stochastic Ordering Results for Consecutive k-out-of-n Systems.
IEEE Transactions on Reliability, 53(1): 7–10.
Boland, P. J., Samaniego, F. J. & Vestrup, E. M. 2003. Linking Dominations and Signatures in Network
Reliabity Theory. In: Lindqvist, B., Doksum, K. (Editors) Mathematical and Statistical Methods in
Reliability. World Scientific, Singapore, pp.89–103.
Boutsikas, M. V. & Koutras, M. V. 2000. Reliability approximation for Markov chain imbeddable systems.
Methodology and Computing in Applied Probability, 2(4): 393–411.
Brown, F. M. 1990. Boolean Reasoning: The Logic of Boolean Equations, Kluwer Academic Publishers,
Boston, USA.
Bryant, R. 1986. Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers,
(8): 677–691.
Chao, M. T. & Fu, J. C. 1989. A limit theorem of certain repairable systems. Annals of the Institute of Statistical
Mathematics, 41: 809–818.
Chao, M. T. & Fu, J. C. 1991. The reliability of large series system under Markov structure, Advances of
Applied Probability, 41: 894–908.
Cochran, J. K. & Lewis, T. P. 2002. Computing small-fleet aircraft availabilities including redundancy and
spares. Computers & Operations Research, 29(5): 529–540.
Crama, Y. & Hammer, P. L. 2011. Boolean functions: Theory, Algorithms, and Applications, Cambridge,
United Kingdom, Cambridge University Press.
Cui, L., Xu, Y. & Zhao, X. 2010. Developments and applications of the finite Markov chain imbedding approach
in reliability. IEEE Transactions on Reliability, 4(59): 685–690.
Dotson, W. & Gobien J., 1979. A new analysis technique for probabilistic graphs, IEEE Transactions on
Circuits and Systems, CAS-26(10): 855–865.
Dutuit, Y. & Rauzy, A. 2001. New insight into the assessment of k-out-of-n and related systems, Reliability
Engineering & System Safety, 72(2): 303–314.
Fu, J. C. 1986. Reliability of consecutive-k-out-of-n: F systems with (k-1)-step Markov dependence. IEEE
Transactions on Reliability, 35(5): 602–606.
Fu, J. C. & Koutras, M. V. 1994. Distribution theory of runs: a Markov chain approach. Journal of the
American Statistical Association, 89(427): 1050–1058
Golnaraghi, F. & Kuo, B. C. 2009. Automatic Control Systems, Ninth Edition, John Wiley & Sons, New
York. NY, USA.
Hiroshima, T., Yamachi, H., Tsujimura, Y., Yamamoto, H. & Kambayashi, Y. 2006. Evaluating ability of
a branch and bound method designed for solving bi-objective NVP design problem. In Advanced Reliability
Modeling II: Reliability Testing and Improvement: Proceedings of the 2nd Asian International
Workshop (AIWARM 2006), Busan, Korea, 24–26 August 2006 (p. 124). World Scientific.
Heidtmann, K. D. 1982. Improved method of inclusion-exclusion applied to k-out-of-n systems, IEEE
Transactions on Reliability, 31(1): 36–40.
Kaufmann, A., Grouchko D. & Cruon R., 1977. Mathematical Methods for the Study of the Reliability of
Systems, Academic Press, New York, NY, USA.
Kochar, K., Mukerjee, H. & Samaniego, F.J. 1999. The ‘signature’ of a coherent system and its application
to comparisons among systems, Naval Research Logistics, 46: 507–523.
Koutras, M. V. 1996. On a Markov chain approach for the study of reliability structures. Journal of Applied
Probability, 33(2): 357–367.
Kuo, W. & Zuo, M. J. 2003. The k-out-of-n System Model. In: Optimal Reliability Modelling: Principles and
Applications, Kuo, W. and M.J. Zuo (Eds.). Chapter 7, John Wiley and Sons, New York, USA, pp: 231–280.
Kvam, P. H. & Pena, E. A. 2005. Estimating load-sharing properties in a dynamic reliability system. Journal
of the American Statistical Association, 100(469), 262–272.
Levitin, G., Xing, L. & Amari, S. V. 2012. Recursive algorithm for reliability evaluation of non-repairable
phased mission systems with binary elements. IEEE Transactions on Reliability, 61(2), 533–542.
Li, S., Si, S., Dui H, Cai Z. & Sun S. 2014. A novel decision diagrams extension method. Reliability
Engineering & System Safety, 126: 107–115.
Liu, H. 1998. Reliability of a load-sharing k-out-of-n: G system: non-iid components with arbitrary distributions.
IEEE Transactions on Reliability, 47(3), 279–284.
Locks, M. O. & Heidtmann, K. D. 1984. Comments and reply on : Improved method of inclusion-exclusion
applied to k-out-of-n systems, IEEE Transaction on Reliability, 33(4): 321–322.
Marichal, J. - L. & Mathonet, P., 2013. Computing system signatures through reliability functions, Statistics
and Probability Letters, 83: 710–717.
Marichal, J. – L., Mathonet, P. & Waldhauser. T. 2011. On signature – based expressions of system reliability,
Journal of Multivariate Analysis, 102(10): 1410–1416.
Milad, M. S., Feceniuk, A. P. & Romankevich, V. A. 2012. The probability of multiprocessor system falling
into dangerous state estimation. Радіоелектронні і комп’ютерні системи (Radio Electronics and Com�-
puter Systems: Journal of the National Technical University of Ukraine), (6): 38–41.
Misra, K. B. 1992. Reliability Analysis and Prediction : A Methodology Oriented Treatment. Elsevier
Science Publishers, Amsterdam, The Netherlands.
Misra, K. B. (Editor), 2008. Handbook of Performability Engineering, Springer, London, UK.
Mo, Y. 2014. A multiple-valued decision-based approach to solve dynamic fault tree. IEEE Transactions on
Reliability, 63(1): 81–93.
Mo, Y., Xing , L. & Amari, S. V. 2014. A multiple-valued decision diagram based method for efficient reliability
analysis of non-repairable phased-mission systems. IEEE Transaction Reliability; 63(1): 320–30.
Mo, Y., Xing , L., Amari, S. V. & Dugan, J. B. 2015. Efficient analysis of multi-state k-out-of-n system,
Reliability Engineering and System Safety, 133: 95–105.
Muroga, S. 1979. Logic Design and Switching Theory, Wiley, New York, NY, USA.
Papadimitratos, P. & Haas, Z. J. 2006. Secure data communication in mobile ad hoc networks. IEEE Jour�-
nal on Selected Areas in Communications, 24(2): 343–356.
Pock M, Malass EO & Walter M. 2011. Combining different binary decision diagram techniques for solving
models with multiple failure states. Journal of Risk and Reliability, 225(1): 18–27.
Rauzy, A. 2008. Binary Decision Diagrams for Reliability Studies, Chapter 25 in Misra, K. B. (Editor), Handbook
of Performability Engineering, Springer, London, UK, pp. 381–396.
Rushdi, A. M. 1983. Symbolic reliability analysis with the aid of variable-entered Karnaugh maps, IEEE
Transactions on Reliability, R-32(2): 134–139.
Rushdi, A. M. 1985. Uncertainty analysis of fault-tree outputs, IEEE Transactions on Reliability, R-34(5):
–462.
Rushdi, A. M. 1986. Utilization of symmetric switching functions in the computation of k-out-of-n system
reliability, Microelectronics and Reliability, 26(5): 973–987.
Rushdi, A. M. 1987. Efficient computation of k-to-l-out-of-n system reliability, Reliability Engineering, vol.
, no. 3, pp. 157 -163, 1987, Erratum : ibid, 19(4): 321, 1987.
Rushdi, A. M. 1990. Threshold systems and their reliability, Microelectronics and Reliability, 30(2):
–312.
Rushdi, A. M. 1991. Comments on : An efficient non-recursive algorithm for computing the reliability of
k-out-of-n systems, IEEE Transactions on Reliability, 40(1): 60–61.
Rushdi, A. M. 1993. Reliability of k-out-of-n Systems, Chapter 5 in Misra, K. B. (Editor), New Trends in
System Reliability Evaluation, Vol. 16, Fundamental Studies in Engineering, Elsevier Science Publishers,
Amsterdam, The Netherlands, pp. 185–227.
Rushdi, A. M. 2010. Partially-redundant systems: Examples, reliability, and life expectancy, International
Magazine on Advances in Computer Science and Telecommunications, 1(1): 1–13.
Rushdi, A. M. & Abdul Ghani, A. A. 1993. A comparison between reliability analyses based primarily on
disjointness or statistical independence : The case of the generalized INDRA network, Microelectronics
and Reliability, 33(7): 965–978.
Rushdi, A.M. & Al-Hindi, K.A. 1993, A table for the lower boundary of the region of useful redundancy for
k-out-of-n systems, Microelectronics and Reliability, 33: 979–992.
Rushdi, A. M. & Al-Khateeb, D. L. 1983. A review of methods for system reliability analysis: A Karnaughmap
perspective, Proceedings of the First Saudi Engineering Conference, Jeddah, Saudi Arabia, 1: 57–95.
Rushdi, A.M. & Al-Qasimi, A.M. 1994. Efficient computation of the P.M.F. and the C.D.F. of the generalized
binomial distribution. Microelectronics and Reliability, 34: 1489–1499.
Rushdi, A. M. & Al-Thubaity, A. O. 1993. Efficient computation of the sensitivity of k-out-of-n system
reliability, Microelectronics and Reliability, 33: 1963–1979.
Rushdi, A. M. & Alturki, A.M. 2015. Reliability of coherent threshold systems. Journal of Applied Science
(3): 431–443.
Rushdi, A. M. & Al-Yahya, 2001. , Derivation of the complete sum of a switching function with the aid
of the variable-entered Karnaugh map, Journal of King Saud University: Engineering Sciences, 13(2):
–269, 2001.
Rushdi, A. M. & Ba-Rukab O. M. 2005a. A doubly-stochastic fault-tree assessment of the probabilities of
security breaches in computer systems, Proceedings of the Second Saudi Science Conference, Part Four:
Computer, Mathematics, and Statistics, Jeddah, Saudi Arabia, pp. 1–17.
Rushdi, A. M. & Ba-Rukab O. M. 2005b. Fault-tree modelling of computer system security, International
Journal of Computer Mathematics, 82(7): 805–819.
Rushdi, A. M. & Ba-Rukab O. M. 2014. Map derivation of the closures for dependency and attribute sets
and all candidate keys for a relational Database, Journal of King Abdulaziz University: Engineering
Sciences, 25(2): 3–34
Rushdi, A. M. & Dehlawi, F. M.-A. 1988. Optimal computation of k-to-l-out-of-n system reliability,
Microelectron. Reliab., vol. 27, no. 5, pp. 875-896, 1987, Erratum : ibid, 28(4): 671.
Rushdi, A. M. & Ghaleb, F. A. 2014. The Walsh spectrum and the real transform of a switching function: A
review with a Karnaugh-map perspective, Journal of Engineering and Computer Sciences, Qassim University,
(2): 73–112.
Rushdi, A. M. & Goda, A. S. 1985. Symbolic reliability analysis via Shannon's expansion and statistical
independence, Microelectronics and Reliability, 25(6): 1041–1053.
Rushdi, A. M. & Hassan, A. K. 2015. Reliability of migration between habitat patches with heterogeneous
ecological corridors, Ecological Modelling, 304: 1-10.
Rushdi, A. M. & Hassan, A. K. 2016a. An exposition of system reliability analysis with an ecological perspective,
Ecological Indicators, 63: 282–295.
Rushdi, A. M. & Hassan, A. K. 2016b. Quantification of uncertainty in the reliability of migration between
habitat patches. Computational Ecology and Software, 6(3): 66–82.
Rushdi, A. M. & Rushdi, M. A. 2016. Switching-Algebraic Analysis of System Reliability. Chapter 6 in M.
Ram and P. Davim (Editors), Advances in Reliability and System Engineering, Management and Industrial
Engineering Series, Springer International Publishing, Cham, Switzerland, pp. 139-161.
Samaniego, F. J. 1985. On Closure of the IFR Class Under Formation of Coherent Systems. IEEE Transactions
on Reliability Theory, R-34: 69–72.
Samaniego, F. J. 2007. System Signatures and their Applications in Engineering Reliability, Springer
Science+Business Media, LLC, New York, NY,USA
Satyanarayana, A. & Prabhakar, A. 1978. A new topological formula and rapid algorithm for reliability
analysis of complex networks. IEEE Transactions on Reliability, R-30: 82–100.
Satyanarayana, A. & Chang, M. K. 1983. Network reliability and the factoring theorem. Networks, 13:
–120.
Scheuer, E. M. 1988. Reliability of an m-out of-n system when component failure induces higher failure rates
in survivors, IEEE Transctions on Reliability, 37(1): 73–74.
Shao, J. & Lamberson, L. R. 1991. Modeling a shared-load k-out-of-n: G system. IEEE Transactions on
Reliability, 40(2): 205–209.
Tian, Z., Zuo, M. J. & Yam, R. C. 2008. Multi-state k-out-of-n systems and their performance evaluation.
IIE Transactions, 41(1): 32–44.
Trivedi, K. S. 2002. Probability and Statistics with Reliability, Queuing, and Computer Science Applications,
nd Ed., Prentice-Hall, Englewood Cliffs, NJ, USA.
Wang, J., Ding, M. & Li, S. 2010. Reliability analysis of converter valves for VSC-HVDC power transmission
system. In 2010 IEEE Asia-Pacific Power and Energy Engineering Conference: 1–4.
Wu, J.-S. & Chen R.-J. 1994. An Algorithm for Computing the Reliability of Weighted-k-out-of-n Systems,
IEEE Transactions on Reliability, 43(2): 327–328.
Yamachi, H. & Yamamoto, H. 2006. Searching Pareto solutions of bi-objective NVP system design problem
with breadth first search method. In 5th IEEE/ACIS International Conference on Computer and Information
Science and 1st IEEE/ACIS International Workshop on Component-Based Software Engineering,
Software Architecture and Reuse (ICIS-COMSAR'06): 252–258.
Yinghui, T. & Jing, Z. 2008. New model for load-sharing k-out-of-n: G system with different components.
Journal of Systems Engineering and Electronics, 19(4), 748–751.
Zhegalov, S. I. 1986. A method of calculating the probability of failure-free operation of a system with
different elements, Soviet Journal of Computer Systems Sciences (Formerly, Engineering. Cybernetics),
(1): 147–149.
Zuo, M., Chiovelli, S. & Huang, J. 1999. Reliability evaluation of furnace systems. Reliability Engineering
& System Safety, 65(3): 283–287.
