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

Anne Katharina Ingrid Remke, Boudewijn R.H.M. Haverkort, L. Cloth

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

## 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.
Original language Undefined First International Conference on Performance Evaluation Methodologies and Tools New York Association for Computing Machinery (ACM) 7 10 1-59593-506-1 https://doi.org/10.1145/1190366.1190372 Published - 11 Oct 2006 1st International Conference on Performance Evaluation Methodologies and Tools 2006 - Pisa, ItalyDuration: 11 Oct 2006 → 13 Oct 2006Conference number: 1http://archive.valuetools.org/2006/

### Publication series

Name ACM 2

### Conference

Conference 1st International Conference on Performance Evaluation Methodologies and Tools 2006 VALUETOOLS 2006 Italy Pisa 11/10/06 → 13/10/06 http://archive.valuetools.org/2006/

## Keywords

• METIS-238165
• EWI-6897
• IR-66348