Solving large interval availability models using a model transformation approach

摘要

Fault-tolerant systems are often modeled using (homogeneous) continuous time Markov chains (CTMCs). Computation of the distribution of the interval availability, i.e. of the distribution of the fraction of time in a time interval in which the system is operational, of a fault-tolerant system modeled by a CTMC is an important problem which has received attention recently. However, currently available methods to perform that computation are very expensive for large models and large time intervals. In this paper, we develop a new method to compute the distribution of the interval availability which, for large enough models and large enough time intervals, is significantly faster than previous methods. In the method, a truncated transformed model, which has with some arbitrarily small error the same interval availability distribution as the original model, is obtained from the original model and the truncated transformed model is solved using a previous state-of-the-art method. The method requires the selection of a "regenerative" state and its performance depends on that selection. For a class of models, including typical failure/repair models of coherent fault-tolerant systems with exponential failure and repair time distributions and repair in every state with failed components, a natural selection for the regenerative state exists and theoretical results are available assessing the performance of the method for that natural selection in terms of "visible" model characteristics. Those results can be used to anticipate when the method can be expected to be competitive for models in that class. Numerical results are presented showing that the new method can indeed be significantly faster than a previous state-of-the-art method and is able to deal with some large models and large time intervals in reasonable CPU times.