Résumé
A dynamic partial order reduction (DPOR) algorithm is optimal when it always explores at most one representative per Mazurkiewicz trace. Existing literature suggests that the reduction obtained by the non-optimal, state-of-the-art Source-DPOR (SDPOR) algorithm is comparable to optimal DPOR. We show the first program with O(n) Mazurkiewicz traces where SDPOR explores O(2 n) redundant schedules. We furthermore identify the cause of this blow-up as an NP-hard problem. Our main contribution is a new approach, called Quasi-Optimal POR, that can arbitrarily approximate an optimal exploration using a provided constant k. We present an implementation of our method in a new tool called Dpu using specialised data structures. Experiments with Dpu, including Debian packages, show that optimality is achieved with low values of k, outperforming state-of-the-art tools.
| langue originale | Anglais |
|---|---|
| Pages (de - à) | 3-33 |
| Nombre de pages | 31 |
| journal | Formal Methods in System Design |
| Volume | 57 |
| Numéro de publication | 1 |
| Les DOIs | |
| état | Publié - juil. 2021 |
| Modification externe | Oui |
Empreinte digitale
Voici les principaux termes ou expressions associés à « Quasi-optimal partial order reduction ». Ces libellés thématiques sont générés à partir du titre et du résumé de la publication. Ensemble, ils forment une empreinte digitale unique.Citer cette ressource
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver