Uniformization with Representatives - comprehensive transient analysis of infinite-state QBDs


Remke, Anne and Haverkort, Boudewijn R. and Cloth, Lucia (2006) Uniformization with Representatives - comprehensive transient analysis of infinite-state QBDs. In: First International Conference on Performance Evaluation Methodologies and Tools, 10 Oct 2006, Pisa, Italy (pp. p. 7).

open access
Abstract:A large variety of computer and communication systems can be modeled adequately as infinite-state continuous-time Markov chains (CTMCs). A highly structured class of such infinite-state CTMCs is the class of Quasi-Birth-Death processes (QBDs), on which we focus in this paper. We present an efficient variant of uniformization for computing the transient probability $\mathbf{V}_{i,j}(t)$ of being in each state $j$ of the QBD for any possible initial state $i$ at time $t$. Note that both the set of starting states and the set of goal states have infinite size. All the probabilities $\mathbf{V}_{i,j}(t)$ are needed in the context of probabilistic model checking. The key idea of our algorithm is to split the infinite set of starting states into a finite part and an infinite (repeating) part. The transient probabilities for the infinite part are then computed using the new notion of \emph{representatives}. We present the required data structures and algorithm, as well as an application-dependent optimal stopping criterion. In
a simple case study we show the feasibility of our approach, as well as the efficiency gain due to the optimal stopping criterion.
Item Type:Conference or Workshop Item
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/66348
Official URL:http://doi.acm.org/10.1145/1190366.1190372
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 238165