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

PDF
173kB 
Abstract:  A large variety of computer and communication systems can be modeled adequately as infinitestate continuoustime Markov chains (CTMCs). A highly structured class of such infinitestate CTMCs is the class of QuasiBirthDeath processes (QBDs), on which we focus in this paper. We present an efficient variant of uniformization for computing the transient probability of being in each state of the QBD for any possible initial state at time . Note that both the set of starting states and the set of goal states have infinite size. All the probabilities 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 . We present the required data structures and algorithm, as well as an applicationdependent 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:  
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 
Repository Staff Only: item control page
Metis ID: 238165