General distributions in process algebra

Joost P. Katoen, P.R. d' Argenio

    Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

    23 Citations (Scopus)

    Abstract

    This paper is an informal tutorial on stochastic process algebras, i.e., process calculi where action occurrences may be subject to a delay that is governed by a (mostly continuous) random variable. Whereas most stochastic process algebras consider delays determined by negative exponential distributions, this tutorial is concerned with the integration of general, non-exponential distributions into a process algebraic setting. We discuss the issue of incorporating such distributions in an interleaving semantics, and present some existing solutions to this problem. In particular, we present a process algebra for the specification of stochastic discrete-event systems modeled as generalized semi-Markov chains (GSMCs). Using this language stochastic discrete-event systems can be described in an and modular way. The operational semantics of this process algebra is given in terms of stochastic automata, a novel mixture of timed automata and GSMCs. We show that GSMCs are a proper subset of stochastic automata, discuss various notions of equivalence, present congruence results, treat equational reasoning, and argue how an expansion law in the process algebra can be obtained. As a case study, we specify the root contention phase within the standardized IEEE 1394 serial bus protocol and study the delay until root contention resolution. An overview of related work on general distributions in process algebra and a discussion of trends and future work complete this tutorial.
    Original languageEnglish
    Title of host publicationLectures on Formal Methods and Performance Analysis
    Subtitle of host publicationFirst EEF/Euro Summer School on Trends in Computer Science Bergen Dal, The Netherlands, July 3–7, 2000 Revised Lectures
    EditorsHendrik Brinksma, H. Hermanns, Joost P. Katoen
    Place of PublicationLondon
    PublisherSpringer
    Pages375-428
    Number of pages54
    ISBN (Electronic)978-3-540-44667-5
    ISBN (Print)978-3-540-42479-6
    DOIs
    Publication statusPublished - 2001

    Publication series

    NameLecture notes in Computer Science
    PublisherSpringer Verlag
    Volume2090

    Keywords

    • FMT-PA: PROCESS ALGEBRAS
    • FMT-FMPA: FORMAL METHODS FOR PERFORMANCE ANALYSIS
    • IR-63272
    • FMT-PM: PROBABILISTIC METHODS
    • EWI-6418

    Fingerprint

    Dive into the research topics of 'General distributions in process algebra'. Together they form a unique fingerprint.

    Cite this