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.

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.

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.