Dynamic Partial Order Reduction Using Probe Sets


Share/Save/Bookmark

Kastenberg, H. and Rensink, A. (2008) Dynamic Partial Order Reduction Using Probe Sets. In: Concurrency Theory (CONCUR), 19-22 Aug 2008, Toronto, Canada (pp. pp. 233-247).

[img] PDF
Restricted to UT campus only
: Request a copy
288kB
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.
Item Type:Conference or Workshop Item
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65022
Official URL:http://dx.doi.org/10.1007/978-3-540-85361-9_21
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 251213