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

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.