zbMATH — the first resource for mathematics

Monotonic partial order reduction: an optimal symbolic partial order reduction technique. (English) Zbl 1242.68166
Bouajjani, Ahmed (ed.) et al., Computer aided verification. 21st international conference, CAV 2009, Grenoble, France, June 26–July 2, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02657-7/pbk). Lecture Notes in Computer Science 5643, 398-413 (2009).
Summary: We present a new technique called monotonic partial order reduction (MPOR) that effectively combines dynamic partial order reduction with symbolic state space exploration for model checking concurrent software. Our technique hinges on a new characterization of partial orders defined by computations of a concurrent program in terms of quasi-monotonic sequences of thread-ids. This characterization, which is of independent interest, can be used both for explicit or symbolic model checking. For symbolic model checking, MPOR works by adding constraints to allow automatic pruning of redundant interleavings in a SAT/SMT solver based search by restricting the interleavings explored to the set of quasi-monotonic sequences. Quasi-monotonicity guarantees both soundness (all necessary interleavings are explored) and optimality (no redundant interleaving is explored) and is, to the best of our knowledge, the only known optimal symbolic POR technique.
For the entire collection see [Zbl 1165.68004].

68Q60 Specification and verification (program logics, model checking, etc.)
Full Text: DOI