On the computational aspects of performability models of fault-tolerant computer systems

It is shown that the (scaled) conditional moments of performability in Markov models are the states of a cascaded, linear, continuous-time dynamic system with identical system matrices in each stage. This interpretation leads to a simple method of computing the first moment for nonhomogeneous Markov models with finite mission time. In addition, the cascaded system representation leads to the derivation of a set of two stable algorithms for propagating the conditional moments of performability in homogeneous Markov models. In particular, a very fast doubling algorithm using diagonal Pade approximation to compute the matrix exponential and repeated squaring is derived. The algorithms are widely recognized, to be superior to those based on eigenvalue analysis in terms of both the computational efficiency and stability. The algorithms have obvious implications in solving reliability/availability models with large mission times