Process algebra for performance evaluation

H. Hermanns, Ulrich Herzog, Joost P. Katoen

    Research output: Contribution to journalArticleAcademicpeer-review

    153 Citations (Scopus)
    36 Downloads (Pure)

    Abstract

    This paper surveys the theoretical developments in the field of stochastic process algebras, process algebras where action occurrences may be subject to a delay that is determined by a random variable. A huge class of resource-sharing systems – like large-scale computers, client–server architectures, networks – can accurately be described using such stochastic specification formalisms. The main emphasis of this paper is the treatment of operational semantics, notions of equivalence, and (sound and complete) axiomatisations of these equivalences for different types of Markovian process algebras, where delays are governed by exponential distributions. Starting from a simple actionless algebra for describing time-homogeneous continuous-time Markov chains, we consider the integration of actions and random delays both as a single entity (like in known Markovian process algebras like TIPP, PEPA and EMPA) and as separate entities (like in the timed process algebras timed CSP and TCCS). In total we consider four related calculi and investigate their relationship to existing Markovian process algebras. We also briefly indicate how one can profit from the separation of time and actions when incorporating more general, non-Markovian distributions.
    Original languageUndefined
    Article number10.1016/S0304-3975(00)00305-4
    Pages (from-to)43-87
    Number of pages44
    JournalTheoretical computer science
    Volume274
    Issue number1-2
    DOIs
    Publication statusPublished - 2002

    Keywords

    • EWI-6398
    • FMT-PM: PROBABILISTIC METHODS
    • IR-66258
    • FMT-PA: PROCESS ALGEBRAS
    • METIS-208751
    • FMT-FMPA: FORMAL METHODS FOR PERFORMANCE ANALYSIS

    Cite this

    Hermanns, H. ; Herzog, Ulrich ; Katoen, Joost P. / Process algebra for performance evaluation. In: Theoretical computer science. 2002 ; Vol. 274, No. 1-2. pp. 43-87.
    @article{d215906201074fbc9a4e4f0855fb629b,
    title = "Process algebra for performance evaluation",
    abstract = "This paper surveys the theoretical developments in the field of stochastic process algebras, process algebras where action occurrences may be subject to a delay that is determined by a random variable. A huge class of resource-sharing systems – like large-scale computers, client–server architectures, networks – can accurately be described using such stochastic specification formalisms. The main emphasis of this paper is the treatment of operational semantics, notions of equivalence, and (sound and complete) axiomatisations of these equivalences for different types of Markovian process algebras, where delays are governed by exponential distributions. Starting from a simple actionless algebra for describing time-homogeneous continuous-time Markov chains, we consider the integration of actions and random delays both as a single entity (like in known Markovian process algebras like TIPP, PEPA and EMPA) and as separate entities (like in the timed process algebras timed CSP and TCCS). In total we consider four related calculi and investigate their relationship to existing Markovian process algebras. We also briefly indicate how one can profit from the separation of time and actions when incorporating more general, non-Markovian distributions.",
    keywords = "EWI-6398, FMT-PM: PROBABILISTIC METHODS, IR-66258, FMT-PA: PROCESS ALGEBRAS, METIS-208751, FMT-FMPA: FORMAL METHODS FOR PERFORMANCE ANALYSIS",
    author = "H. Hermanns and Ulrich Herzog and Katoen, {Joost P.}",
    year = "2002",
    doi = "10.1016/S0304-3975(00)00305-4",
    language = "Undefined",
    volume = "274",
    pages = "43--87",
    journal = "Theoretical computer science",
    issn = "0304-3975",
    publisher = "Elsevier",
    number = "1-2",

    }

    Hermanns, H, Herzog, U & Katoen, JP 2002, 'Process algebra for performance evaluation', Theoretical computer science, vol. 274, no. 1-2, 10.1016/S0304-3975(00)00305-4, pp. 43-87. https://doi.org/10.1016/S0304-3975(00)00305-4

    Process algebra for performance evaluation. / Hermanns, H.; Herzog, Ulrich; Katoen, Joost P.

    In: Theoretical computer science, Vol. 274, No. 1-2, 10.1016/S0304-3975(00)00305-4, 2002, p. 43-87.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Process algebra for performance evaluation

    AU - Hermanns, H.

    AU - Herzog, Ulrich

    AU - Katoen, Joost P.

    PY - 2002

    Y1 - 2002

    N2 - This paper surveys the theoretical developments in the field of stochastic process algebras, process algebras where action occurrences may be subject to a delay that is determined by a random variable. A huge class of resource-sharing systems – like large-scale computers, client–server architectures, networks – can accurately be described using such stochastic specification formalisms. The main emphasis of this paper is the treatment of operational semantics, notions of equivalence, and (sound and complete) axiomatisations of these equivalences for different types of Markovian process algebras, where delays are governed by exponential distributions. Starting from a simple actionless algebra for describing time-homogeneous continuous-time Markov chains, we consider the integration of actions and random delays both as a single entity (like in known Markovian process algebras like TIPP, PEPA and EMPA) and as separate entities (like in the timed process algebras timed CSP and TCCS). In total we consider four related calculi and investigate their relationship to existing Markovian process algebras. We also briefly indicate how one can profit from the separation of time and actions when incorporating more general, non-Markovian distributions.

    AB - This paper surveys the theoretical developments in the field of stochastic process algebras, process algebras where action occurrences may be subject to a delay that is determined by a random variable. A huge class of resource-sharing systems – like large-scale computers, client–server architectures, networks – can accurately be described using such stochastic specification formalisms. The main emphasis of this paper is the treatment of operational semantics, notions of equivalence, and (sound and complete) axiomatisations of these equivalences for different types of Markovian process algebras, where delays are governed by exponential distributions. Starting from a simple actionless algebra for describing time-homogeneous continuous-time Markov chains, we consider the integration of actions and random delays both as a single entity (like in known Markovian process algebras like TIPP, PEPA and EMPA) and as separate entities (like in the timed process algebras timed CSP and TCCS). In total we consider four related calculi and investigate their relationship to existing Markovian process algebras. We also briefly indicate how one can profit from the separation of time and actions when incorporating more general, non-Markovian distributions.

    KW - EWI-6398

    KW - FMT-PM: PROBABILISTIC METHODS

    KW - IR-66258

    KW - FMT-PA: PROCESS ALGEBRAS

    KW - METIS-208751

    KW - FMT-FMPA: FORMAL METHODS FOR PERFORMANCE ANALYSIS

    U2 - 10.1016/S0304-3975(00)00305-4

    DO - 10.1016/S0304-3975(00)00305-4

    M3 - Article

    VL - 274

    SP - 43

    EP - 87

    JO - Theoretical computer science

    JF - Theoretical computer science

    SN - 0304-3975

    IS - 1-2

    M1 - 10.1016/S0304-3975(00)00305-4

    ER -