Numerical Methods for Reliability Evaluation of Markov Closed Fault-Tolerant Systems

This paper compares three numerical methods for reliability calculation of Markov, closed, fault-tolerant systems which give rise to continuous-time, time-homogeneous, finite-state, acyclic Markov chains. We consider 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, and a third-order implicit Runge-Kutta method (an ordinary-differential-equation solution method). Modifications to Jensen's method include incorporating stable calculation of Poisson probabilities and steady-state detection of the underlying discrete-time Markov chain. The new version of Jensen's method is not only more efficient but yields more accurate results. Modifications to ACE algorithm are proposed which incorporate scaling and other refinements to make it more stable & accurate. However, the new version no longer yields solution symbolic with respect to time variable. Implicit Runge-Kutta method can exploit the acyclic structure of the Markov chain and therefore becomes more efficient. 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 upon 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 Markov chains. However, this method can suffer severely from numerical instabilities if the generator matrix has many distinct diagonal elements. This prevents it from being a general purpose, reliable, numerical solution technique. • For modified Jensen's method, the acyclic structure of the Markov chain cannot be exploited (to the best of our knowledge). However, its computation complexity can be a priori determined for acyclic case (which cannot be done for Markov chains with cycles). For non-stiff models, modified Jensen's method is more efficient than implicit Runge-Kutta method adapted to acyclic Markov chains. However, as 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 method is less efficient than the third-order implicit Runge-Kutta method. ©1995 IEEE

Duke Scholars

Author Kishor S. Trivedi Electrical and Computer Engineering