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.

Preview

PDF
169Kb

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
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Design and Analysis of Communication Systems (DACS)
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 EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 238165