First passage time analysis of stochastic process algebra using partial orders

Theo C. Ruys, Rom Langerak, Joost-Pieter Katoen, Diego Latella, Mieke Massink

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    6 Citations (Scopus)
    18 Downloads (Pure)

    Abstract

    This paper proposes a partial-order semantics for a stochastic process algebra that supports general (non-memoryless) distributions and combines this with an approach to numerically analyse the first passage time of an event. Based on an adaptation of McMillan's complete finite prefix approach tailored to event structures and process algebra, finite representations are obtained for recursive processes. The behaviour between two events is now captured by a partial order that is mapped on a stochastic task graph, a structure amenable to numerical analysis. Our approach is supported by the (new) tool FOREST for generating the complete prefix and the (existing) tool PEPP for analysing the generated task graph. As a case study, the delay of the first resolution in the root contention phase of the IEEE 1394 serial bus protocol is analysed.
    Original languageEnglish
    Title of host publicationTools and Algorithms for the Construction and Analysis of Systems
    Subtitle of host publication7th International Conference, TACAS 2001, held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001, Genova, Italy, April 2–6, 2001. Proceedings
    Place of PublicationBerlin, Heidelberg
    PublisherSpringer
    Pages220-235
    Number of pages16
    ISBN (Electronic)978-3-540-45319-2
    ISBN (Print)978-3-540-41865-8
    DOIs
    Publication statusPublished - 2001
    Event7th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2001 - Genova, Italy
    Duration: 2 Apr 20016 Apr 2001
    Conference number: 7

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume2031
    ISSN (Print)0302-9743

    Workshop

    Workshop7th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2001
    Abbreviated titleTACAS
    CountryItaly
    CityGenova
    Period2/04/016/04/01

    Keywords

    • FMT-RT: VERIFICATION OF REAL-TIME SYSTEMS
    • FMT-FMPA: FORMAL METHODS FOR PERFORMANCE ANALYSIS
    • FMT-NIM: NON-INTERLEAVING MODELS
    • FMT-PM: PROBABILISTIC METHODS

    Fingerprint Dive into the research topics of 'First passage time analysis of stochastic process algebra using partial orders'. Together they form a unique fingerprint.

    Cite this