NUMERICAL-METHODS FOR RELIABILITY EVALUATION OF MARKOV CLOSED FAULT-TOLERANT SYSTEMS

This paper compares three numerical methods for reliability calculatio n of Markov, closed, fault-tolerant systems which give rise to continu ous-time, time-homogeneous, finite-state, acyclic Markov chains. We co nsider a modified version of Jensen's method (a probabilistic method, also known as uniformization or randomization), a new version of ACE ( Acyclic Markov Chain Evaluator) algorithm with several enhancements, a nd a third-order implicit Runge-Kutta method (an ordinary-differential -equation solution method). Modifications to Jensen's method include i ncorporating stable calculation of Poisson probabilities and steady-st ate detection of the underlying discrete-time Markov chain. The new ve rsion of Jensen's method is not only more efficient but yields more ac curate results. Modifications to ACE algorithm are proposed which inco rporate scaling and other refinements to make it more stable & accurat e. However, the new version no longer yields solution symbolic with re spect to time variable. Implicit Runge-Kutta method can exploit the ac yclic structure of the Markov chain and therefore becomes more efficie nt. All three methods are implemented. Several reliability models are numerically solved using these methods and the results are compared on the basis of accuracy and computation cost. Based upon these results, we conclude: The computation cost of ACE algorithm does not depend up on mission time, error tolerance, or eigen-structure of the generator matrix. Our experiments indicate that the numerically refined version of this method can be effectively used for a large class of acyclic Ma rkov chains. However, this method can suffer severely from numerical i nstabilities if the generator matrix has many distinct diagonal elemen ts. This prevents it from being a general purpose, reliable, numerical solution technique. For modified Jensen's method, the acyclic structu re of the Markov chain cannot be exploited (to the best of our knowled ge). However, its computation complexity can be a priori determined fo r acyclic case (which cannot be done for Markov chains with cycles). F or non-stiff models, modified Jensen's method is more efficient than i mplicit Rung-Kutta method adapted to acyclic Markov chains. However, a s model stiffness increases, the adapted version of the implicit Runge -Kutta method becomes more efficient than the modified Jensen's method . We experimented with an adapted version (for acyclic case) of third- order generalized Runge-Kutta method (Malhotra, 1991). However, this m ethod is less efficient than the third-order implicit Runge-Kutta meth od.