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.