We develop a new randomization-based general-purpose method for the computation of the interval availability distribution of systems modeled by continuous-time Markov chains (CTMCs). The basic idea of the new method is the use of a randomization construct with different randomization rates for up and down states. The new method is numerically stable and computes the measure with well-controlled truncation error. In addition, for large CTMC models, when the maximum output rates from up and down states are significantly different, and when the interval availability has to be guaranteed to have a level close to one, the new method is significantly or moderately less costly in terms of CPU time than a previous randomization-based state-of-the-art method, depending on whether the maximum output rate from down states is larger than the maximum output rate from up states, or vice versa. Otherwise, the new method can be more costly, but a relatively inexpensive for large models switch of reasonable quality can be easily developed to choose the fastest method. Along the way, we show the correctness of a generalized randomization construct, in which arbitrarily different randomization rates can be associated with different states, for both finite CTMCs with infinitesimal generator and uniformizable CTMCs with denumerable state space.

This paper is concerned with the computation of the interval availability (proportion of time in a time interval in which the system is up) distribution of a fault-tolerant system modeled by a finite (homogeneous) continuous-time Markov chain (CTMC). General-purpose methods for performing that computation tend to be very expensive when the CTMC and the time interval are large. Based on a previously available method (regenerative transformation) for computing the interval availability complementary distribution, we develop a method called bounding regenerative transformation for the computation of bounds for that measure. Similar to regenerative transformation, bounding regenerative transformation requires the selection of a regenerative state. The method is targeted at a certain class of models, including both exact and bounding failure/repair models of fault-tolerant systems with increasing structure function, with exponential failure and repair time distributions and repair in every state with failed components having failure rates much smaller than repair rates (F/R models), with a “natural” selection for the regenerative state. The method is numerically stable and computes the bounds with well-controlled error. For models in the targeted class and the natural selection for the regenerative state, computational cost should be traded off with bounds tightness through a control parameter. For large models in the class, the version of the method that should have the smallest computational cost should have small computational cost relative to the model size if the value above which the interval availability has to be guaranteed to be is close to 1. In addition, under additional conditions satisfied by F/R models, the bounds obtained with the natural selection for the regenerative state by the version that should have the smallest computational cost seem to be tight for all time intervals or not small time intervals, depending on whether the initial probability distribution of the CTMC is concentrated in the regenerative state or not. CORRECTED VERSION OF RECORD, SEE LAST PAGE OF ARTICLE

Markov reward models have interesting modeling applications, particularly those addressing fault-tolerant hardware/software systems. In this paper, we consider a Markov reward model with a reward structure including only reward rates associated with states, in which both positive and negative reward rates are present and null reward rates are allowed, and develop a numerical method to compute the distribution function of the cumulative reward till exit of a subset of transient states of the model. The method combines a model transformation step with the solution of the transformed model using a randomization construction with two randomization rates. The method introduces a truncation error, but that error is strictly bounded from above by a user-specified error control parameter. Further, the method is numerically stable and takes advantage of the sparsity of the infinitesimal generator of the transformed model. Using a Markov reward model of a fault-tolerant hardware/software system, we illustrate the application of the method and analyze its computational cost. Also, we compare the computational cost of the method with that of the (only) previously available method for the problem. Our numerical experiments seem to indicate that the new method can be efficient and that for medium size and large models can be substantially faster than the previously available method.

The paper "performability analysis: a new algorithmrdquo describes an algorithm for computing the complementary distribution of the accumulated reward over an interval of time in a homogeneous Markov process. In this comment, we show that in two particular cases, one of which is quite frequent, small modifications of the algorithm may reduce significantly its storage complexity.

In this paper, we develop a combinatorial method for the evaluation of the functional yield of defect-tolerant systems-on-chip (SoC). The method assumes that random manufacturing defects are produced according to a model in which defects cause the failure of given components of the system following a distribution common to all defects. The distribution of the number of defects is arbitrary. The yield is obtained by conditioning on the number of defects that result in the failure of some component and performing recursive computations over a reduced ordered binary decision diagram (ROBDD) representation of the fault-tree function of the system. The method has excellent error control. Numerical experiments seem to indicate that the method is efficient and, with some exceptions, allows the analysis with affordable computational resources of systems with very large numbers of components.

Two clarifications are needed. The Laplace transform inversion algorithm used in the numerical method described in the paper [1] differs essentially from the one implemented in the DLAINV FORTRAN subroutine described in [27] only in that: (1) the discretizacion error is strictly controlled using the values for a given by the third displayed equation on page 94, left column and the first two displayed equations on page 94, right column; (2) T is taken equal to 8t instead of 16t; (3) the series accelerated by the epsilon algorithm is the one given by the last displayed equation on page 92, right column, with the shift described after that equation; and (4) Brzinski's recursion described in [29] is used when important cancellations are detected in the standard implementation of the epsilon algorithm. The results for the C.mmp system example were obtained for λP = λM = 10−4 h−1, λS = 10−6 h−1 and μP = μM = μS = 1 h−1, and RRL was run taking as regenerative state the single state without failed components.

Various corrections to the above titled paper (ibid., vol. 55, no. 2, pp. 207-236) are presented. The corrections do not propagate to any other part of the paper and do not affect the correctness of the experimental results reported in the paper.

Markov models are often used to evaluate dependability attributes of fault-tolerant computer systems. The use in practice of Markov models is, however, hampered by the well-known state space explosion problem. Simulation alleviates the problem. For Markov models of repairable fault-tolerant systems, standard simulation of dependability measures tends to be expensive due to the rarity of the system failure event. Importance sampling can speed up the simulation. This paper develops two importance sampling schemes, called failure transition distance biasing & balanced failure transition distance biasing, which exploit the failure transition distance concept in an attempt to improve the efficiency of two other schemes, failure biasing & and balanced failure biasing. The schemes require the computation of the so-called failure transition distances, and procedures to perform those computations are developed. The presentation is tied to a previously proposed measure-specific simulation method for the steady-state unavailability. An optimization method of the parameters of the importance sampling schemes is also developed. For the simulation of the steady-state unavailability, failure transition distance biasing has (as failure biasing) the bounded relative error property for balanced fault-tolerant systems & balanced failure transition distance biasing has (as balanced failure biasing) the bounded relative error property for both balanced & unbalanced fault-tolerant systems. It is proved that, for balanced fault-tolerant systems, both failure transition distance biasing & balanced failure transition distance biasing can indeed improve the efficiency of failure biasing & balanced failure biasing. In addition, numerical experiments seem to indicate that, for unbalanced fault-tolerant systems, balanced failure transition distance biasing can also improve the efficiency of balanced failure biasing. The application of the failure transition distance-based importance sampling schemes is, however, limited to systems not having too many minimal failure covers, or, at least, not having too many minimal failure covers of small cardinality. A minimal failure cover is a minimal bag of failure bags such that the failure of its components implies the failure of the system; a failure bag is any non-empty bag of component classes which can fail simultaneously.

Rewarded homogeneous continuous-time Markov chain (CTMC) models can be used to analyze performance, dependability and performability attributes of computer and telecommunication systems. In this paper, we consider rewarded CTMC models with a reward structure including reward rates associated with states and two measures summarizing the behavior in time of the resulting reward rate random variable: the expected transient reward rate at time t and the expected averaged reward rate in the time interval [0, t]. Computation of those measures can be performed using the randomization method, which is numerically stable and has good error control. However, for large stiff models, the method is very expensive. Exploiting the existence of a quasistationary distribution in the subset of transient states of discrete-time Markov chains with a certain structure, we develop a new variant of the (standard) randomization method, randomization with quasistationarity detection, covering finite CTMC models with state space S/spl cup/{f/sub 1/,f/sub 2/,..., f/sub A/}, A/spl ges/1, where all states in S are transient and reachable among them and the states f/sub i/ are absorbing. The method has the same good properties as the standard randomization method and can be much more efficient. We also compare the performance of the method with that of regenerative randomization.

RAID (Redundant Array of Inexpensive Disks) are widely used in storage servers. Level-5 RAID is one of the most popular RAID architectures. Numerical analysis of exact Markovian dependability models of level-5 RAID architectures with orthogonal organization is unfeasible for many realistic model parameters due to the size of the resulting state space. In this paper we develop approximate dependability models for a level-5 RAID architecture with orthogonal organization which have small state spaces. We consider two measures: the steady-state unavailability and the unreliability. The models encompass disk hot spares and imperfect disk reconstruction. Using bounding techniques we analyze the accuracy of the models and show that the models are extremely accurate. 1.

In this paper we develop a combinatorial method for the evaluation of yield of fault-tolerant systems-on-chip. The method assumes that defects are produced according to a model in which defects are lethal and affect given components of the system following a distribution common to all defects. The distribution of the number of defects is arbitrary. The method is based on the formulation of the yield as 1 minus the probability that a given boolean function with multiple-valued variables has value 1. That probability is computed by analyzing a ROMDD (reduced ordered multiple-valuedecision diagram) representation of the function. For efficiency reasons, we first build a coded ROBDD (reduced ordered binary decision diagram) representation of the function and then transform that coded ROBDD into the ROMDD required by the method. We present numerical experiments showing that the method is able to cope with quite large systems in moderate CPU times.

In this paper we develop a variant, regenerative randomization with Laplace transform inversion, of a previously proposed method (the regenerative randomization method) for the transient analysis of rewarded continuous time Markov models. Those models find applications in dependability and performability analysis of computer and telecommunication systems. The variant differs from regenerative randomization in that the truncated transformed model obtained in that method is solved using a Laplace transform inversion algorithm instead of standard randomization. As regenerative randomization, the variant requires the selection of a regenerative state on which the performance of the method depends. For a class of models, class C$'$, including typical failure/repair models, a natural selection for the regenerative state exists and, with that selection, theoretical results are available assessing the performance of the method in terms of ‘visible’ characteristics. Using dependability class C$'$ models of moderate size of a RAID 5 architecture we compare the performance of the variant with those of regenerative randomization and randomization with steady-state detection for irreducible models, and with those of regenerative randomization and standard randomization for models with absorbing states. For irreducible models, the new variant seems to be about as fast as randomization with steady-state detection for models which are not too small when the initial probability distribution is concentrated in the regenerative state, and significantly faster than regenerative randomization when the model is stiff and not very large. For stiff models with absorbing states, the new variant is much faster than standard randomization and significantly faster than regenerative randomization when the model is not very large. In addition, the variant seems to be able to achieve stringent accuracy levels safely.

Markov models are commonly used to asses the dependability/performability of fault-tolerant systems. Computation of many dependability/performability measures for repairable fault-tolerant systems requires the transient analysis of irreducible Markov models. Examples of such measures are the unavailability at time t and the s-expected interval unavailability at time t. Randomization (also called uniformization) is a well-known Markov transient analysis method and has good properties: numerical stability, well-controlled computation error, and ability to specify the computation error in advance. However, the randomization method is computationally expensive when the model is stiff, as is the case for Markov models of repairable fault-tolerant systems when the mission time of interest is large. Steady-state detection is a technique proposed to speedup randomization when the model is irreducible. This paper points out that another method, regenerative randomization, which has the same good properties as randomization, also covers irreducible models, and compares, for the important class of irreducible failure/repair models with exponential failure and repair time distributions and repair in every state with failed components, the efficiency of the regenerative randomization method with that of randomization with steady-state detection. In the frequent case in which the initial state is the state without failed components the regenerative randomization method can be faster than randomization with steady-state detection, especially when the model is large and the failure rates are much smaller than the repair rates. For other initial probability distributions, the regenerative randomization method seems to perform worse than randomization with steady-state detection.

The transient analysis of large continuous time Markov reliability models of repairable fault-tolerant systems is computationally expensive due to model stiffness. We develop and analyze a method to compute bounds for a measure defined on a particular, but quite wide class of continuous time Markov models, encompassing both exact and bounding continuous time Markov reliability models of fault-tolerant systems. The method is numerically stable and computes the bounds with well-controlled and specifiable-in-advance error. Computational effort can be traded off with bounds accuracy. For a class of continuous time Markov models, class C", including typical failure/repair reliability models with exponential failure and repair time distributions and repair in every state with failed components, the method can yield reasonably tight bounds at a very small computational cost. The method builds upon a recently proposed numerical method for the transient analysis of continuous time Markov models called regenerative randomization.

CTMC (continuous-time Markov chains) are a commonly used formalism for modeling fault-tolerant systems. One of the major drawbacks of CTMC is the well-known state-space explosion problem. This paper develops and analyzes a method (SC-BM) to compute bounds for the reliability of nonrepairable fault-tolerant systems in which only a portion of the state space of the CTMC is generated. SC-BM uses the failure distance concept as the method described previously by the authors (1997) but, unlike that method, which is based on the computation of exact failure distances, SC-BM uses lower bounds for failure distances, which are computed on the system fault-tree, avoiding the computation and holding of all minimal cuts as required in the earlier work. This is important because computation of all minimal cuts is NP-hard and the number of minimal cuts can be very large. In some cases SC-BM gives exactly the same bounds as the previous method; in other cases it gives less tight bounds. SC-BM computes tight bounds for the reliability of quite complex systems with an affordable number of generated states for short to quite large mission times. The analysis of several examples seems to show that the bounds obtained by SC-BM appreciably outperform those obtained by simpler methods, and, when they are not equal, are only slightly worse than the bounds obtained by the previous method. In addition, the overhead in CPU time due to computing lower bounds for failure distances seems to be reasonable.

We propose an algorithm to compute bounds for the steady-state unavailability using continuous-time Markov chains, which is based on the failure distance concept. The algorithm generates incrementally a subset of the state space until the tightness of the bounds is the specified one. In contrast with a previous algorithm also based on the failure distance concept, the proposed algorithm uses lower bounds for failure distances which are computed on the fault tree of the system, and does not require the knowledge of the minimal cuts. This is advantageous when the number of minimal cuts is large or their computation is time-consuming.

A realistic modeling of fault-tolerant systems requires to take into account phenomena such as the dependence of component failure rates and coverage parameters on the operational configuration of the system, which cannot be properly captured using combinatoric techniques. Such dependencies can be modeled with detail using continuous-time Markov chains (CTMCs). However, the use of CTMC models is limited by the well-known state space exploitation problem. We develop a method for the computation of bounds for the reliability of non-repairable fault-tolerant systems which requires the generation of only a subset of states. The tightness of the bounds increases as more detailed states are generated. The method uses the failure distance concept and is illustrated using an example of a quite complex fault-tolerant system whose failure behavior has the above mentioned types of dependencies.

Recently, a method to bound the steady-state availability using the failure distance concept has been proposed. In this paper we refine that method by introducing state space exploration techniques. In the methods proposed here, the state space is incrementally generated based on the contributions to the steady-state availability band of the states in the frontier of the currently generated state space. Several state space exploration algorithms are evaluated in terms of bounds quality and memory and CPU time requirements. The more efficient seems to be a waved algorithm which expands transition groups. We compare our new methods with the method based on the failure distance concept without state exploration and a method proposed by Souza e Silva and Ochoa which uses state space exploration but does not use the failure distance concept. Using typical examples we show that the methods proposed here can be significantly more efficient than any of the previous methods.

Randomization is a popular method for the transient solution of continuous-time Markov models. Its primary advantages over other methods (i.e., ODE solvers) are robustness and ease of implementation. It is however well-known that the performance of the method deteriorates with the "stiffness" of the model: the number of required steps to solve the model up to time t tends to Λt for Λt → ∞. In this paper we present a new method called regenerative randomization and apply it to the computation of two transient measures for rewarded irreducible Markov models. Regarding the number of steps required in regenerative randomization we prove that: 1) it is smaller than the number of steps required in standard randomization when the initial distribution is concentrated in a single state, 2) for Λt → ∞, it is upper bounded by a function O(log(Λt/ε)), where ε is the desired relative approximation error bound. Using dependability and performability examples we analyze the performance of the method.

Simulation methods for the solution of the extremely large Markovian dependability models which result from complex fault-tolerant computer systems have recently been developed. The author presents efficient simulation methods for the estimation of transient reliability/availability metrics for repairable fault-tolerant computer systems which combine estimator decomposition techniques with an efficient importance sampling technique. Comparison with simulation methods previously proposed for the same type of metrics and models shows that the proposed methods are orders of magnitude faster.>