Skip to main content

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

Publication ,  Journal Article
Lindemann, C; Malhotra, M; Trivedi, KS
Published in: IEEE Transactions on Reliability
January 1, 1995

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

Published In

IEEE Transactions on Reliability

DOI

EISSN

1558-1721

ISSN

0018-9529

Publication Date

January 1, 1995

Volume

44

Issue

4

Start / End Page

694 / 704

Related Subject Headings

  • Operations Research
  • 4612 Software engineering
  • 4010 Engineering practice and education
  • 0906 Electrical and Electronic Engineering
  • 0803 Computer Software
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Lindemann, C., Malhotra, M., & Trivedi, K. S. (1995). Numerical Methods for Reliability Evaluation of Markov Closed Fault-Tolerant Systems. IEEE Transactions on Reliability, 44(4), 694–704. https://doi.org/10.1109/24.476004
Lindemann, C., M. Malhotra, and K. S. Trivedi. “Numerical Methods for Reliability Evaluation of Markov Closed Fault-Tolerant Systems.” IEEE Transactions on Reliability 44, no. 4 (January 1, 1995): 694–704. https://doi.org/10.1109/24.476004.
Lindemann C, Malhotra M, Trivedi KS. Numerical Methods for Reliability Evaluation of Markov Closed Fault-Tolerant Systems. IEEE Transactions on Reliability. 1995 Jan 1;44(4):694–704.
Lindemann, C., et al. “Numerical Methods for Reliability Evaluation of Markov Closed Fault-Tolerant Systems.” IEEE Transactions on Reliability, vol. 44, no. 4, Jan. 1995, pp. 694–704. Scopus, doi:10.1109/24.476004.
Lindemann C, Malhotra M, Trivedi KS. Numerical Methods for Reliability Evaluation of Markov Closed Fault-Tolerant Systems. IEEE Transactions on Reliability. 1995 Jan 1;44(4):694–704.

Published In

IEEE Transactions on Reliability

DOI

EISSN

1558-1721

ISSN

0018-9529

Publication Date

January 1, 1995

Volume

44

Issue

4

Start / End Page

694 / 704

Related Subject Headings

  • Operations Research
  • 4612 Software engineering
  • 4010 Engineering practice and education
  • 0906 Electrical and Electronic Engineering
  • 0803 Computer Software