Automated compositional Markov chain generation for a plain-old telephone system

Holger Hermanns, Joost-Pieter Katoen

    Research output: Contribution to journalArticleAcademicpeer-review

    63 Citations (Scopus)


    Obtaining performance models, like Markov chains and queueing networks, for systems of significant complexity and magnitude is a difficult task that is usually tackled using human intelligence and experience. This holds in particular for performance models of a highly irregular nature. In this paper we argue by means of a non-trivial example – a plain-old telephone system (POTS) – that a stochastic extension of process algebra can diminish these problems by permitting an automatic generation of Markov chains. We introduce a stochastic process algebra that separates the advance of time and action occurrences. For the sake of specification convenience we incorporate an elapse operator that allows the modular description of time constraints where delays are described by continuous phase-type distributions. Using this language we provide a formal specification of the POTS and show how a stochastic process of more than 107 states is automatically obtained from this system description. Finally, we aggregate this model compositionally using appropriate stochastic extensions of (strong and weak) bisimulation. As a result we obtain a highly irregular Markov chain of about 700 states in an automated way, which we use to carry out a transient performance analysis of the POTS.
    Original languageEnglish
    Pages (from-to)97-127
    Number of pages31
    JournalScience of computer programming
    Issue number1
    Publication statusPublished - 2000


    • Automatic Markov chain generation
    • Compositional aggregation
    • Constraint-oriented specification
    • Performance analysis
    • Plain-old telephone system
    • Stochastic process algebra


    Dive into the research topics of 'Automated compositional Markov chain generation for a plain-old telephone system'. Together they form a unique fingerprint.

    Cite this