Bounded relative error in estimating transient measures of highly dependable non-Markovian systems
- 1 April 1994
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Modeling and Computer Simulation
- Vol. 4 (2), 137-164
- https://doi.org/10.1145/175007.175008
Abstract
This article deals with fast simulation techniques for estimating transient measures in highly dependable systems. The systems we consider of components with generally distributed lifetimes and repair times, with complex interaction among components. As is well known, standard simulation of highly dependable systems is very inefficient, and importance-sampling is widely used to improve efficiency. We present two new techniques, one of which is based on the uniformization approach to simulation, and the other is a natural extension of the uniformization approach which we call exponential transformation. We show that under certain assumptions, these techniques have the bounded relative error property, i.e., the relative error of the simulation estimate remains bounded as components become more and more reliable, unlike standard simulation in which it tends to infinity. This implies that only a fixed number of observations are required to achieve a given relative error, no matter how rare the failure events are.Keywords
This publication has 21 references indexed in Scilit:
- A unified framework for simulating Markovian models of highly dependable systemsIEEE Transactions on Computers, 1992
- Optimally efficient estimation of the statistics of rare events in queueing networksIEEE Transactions on Automatic Control, 1991
- Discrete-Time Conversion for Simulating Finite-Horizon Markov ProcessesSIAM Journal on Applied Mathematics, 1990
- Error Bounds for Exponential Approximations of Geometric ConvolutionsThe Annals of Probability, 1990
- Importance Sampling for Stochastic SimulationsManagement Science, 1989
- A GSMP formalism for discrete event systemsProceedings of the IEEE, 1989
- Modeling and analysis of computer system availabilityIBM Journal of Research and Development, 1987
- The hybrid automated reliability predictorJournal of Guidance, Control, and Dynamics, 1986
- Asymptotic methods in reliability theory: a reviewAdvances in Applied Probability, 1984
- Ultrahigh Reliability Prediction for Fault-Tolerant Computer SystemsIEEE Transactions on Computers, 1983