Dynamic Partial Order Reduction Using Probe Sets

H. Kastenberg, Arend Rensink

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

    8 Citations (Scopus)

    Abstract

    We present an algorithm for partial order reduction in the context of a countable universe of deterministic actions, of which finitely many are enabled at any given state. This means that the algorithm is suited for a setting in which resources, such as processes or objects, are dynamically created and destroyed, without an a priori bound. The algorithm relies on abstract enabling and disabling relations among actions, rather than associated sets of concurrent processes. It works by selecting so-called probe sets at every state, and backtracking in case the probe is later discovered to have missed some possible continuation. We show that this improves the potential reduction with respect to persistent sets. We then instantiate the framework by assuming that states are essentially sets of entities (out of a countable universe) and actions test, delete and create such entities. Typical examples of systems that can be captured in this way are Petri nets and (more generally) graph transformation systems. We show that all the steps of the algorithm, including the estimation of the missed actions, can be effectively implemented for this setting.
    Original languageUndefined
    Title of host publicationConcurrency Theory (CONCUR)
    EditorsF. Van Breughel, M. Chechik
    Place of PublicationBerlin
    PublisherSpringer
    Pages233-247
    Number of pages15
    ISBN (Print)978-3-540-85360-2
    DOIs
    Publication statusPublished - 2008
    Event19th International Conference on Concurrency Theory, CONCUR 2008 - Toronto, Canada
    Duration: 19 Aug 200822 Aug 2008
    Conference number: 19

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer Verlag
    NumberSupplement
    Volume5201
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference19th International Conference on Concurrency Theory, CONCUR 2008
    Abbreviated titleCONCUR
    CountryCanada
    CityToronto
    Period19/08/0822/08/08

    Keywords

    • EWI-13555
    • IR-65022
    • METIS-251213

    Cite this

    Kastenberg, H., & Rensink, A. (2008). Dynamic Partial Order Reduction Using Probe Sets. In F. Van Breughel, & M. Chechik (Eds.), Concurrency Theory (CONCUR) (pp. 233-247). [10.1007/978-3-540-85361-9_21] (Lecture Notes in Computer Science; Vol. 5201, No. Supplement). Berlin: Springer. https://doi.org/10.1007/978-3-540-85361-9_21