Interactive Markov Chains

This chapter deals with a particular class of stochastic models that form a cornerstone of this book. Stochastic models are widely used to describe phenomena that change randomly as time progresses.We focus onMarkov chains, as simple and adequate models for many such phenomena. More precise, we cover discrete—as well as continuous-time Markov chains. We discuss details of their analysis to set the ground for the requirements of later chapters, and introduce useful equivalence relations for both types of models. These relations are defined in the style of bisimilarity and are akin to the notion lumpability on Markov chains. Furthermore, we present efficient algorithms to compute these relations, which, as a side result, can be used to compute the ‘best possible’ lumping of a given Markov chain.

In this chapter we use Interactive Markov Chains to investigate some illustrative examples and case studies. We first study the effect of symmetric composition by means of a simple producer—consumer example. In particular, we compare the growth of the state space to other methods to generate an aggregated state space. In a second case study, we use IMC to model a real world application, namely an ordinary telephony system. The constraint oriented specification of time dependencies will be a central issue. In order to circumvent state space sizes of more than 10 millions of states we make excessive use of the theoretical properties and concepts achieved so far, and obtain a Markov chain of manageable size. These two case studies show how performance estimation can be based on a Markov chain obtained from a highly modular and hierarchical IMC specification. A third example will then be used to highlight some implicit limitations to this approach. In particular, the issue of nondeterminism will discussed.

This chapter gives a retrospective view on the main contributions of this book. It summarises the major building blocks of compositional performance and dependability estimation with Interactive Markov Chains, and addresses the general question whether the challenge of compositional performance and dependability estimation has been met. In addition, we point out relevant directions for further work.