Passer à la navigation principale Passer à la recherche Passer au contenu principal

Quasi-optimal partial order reduction

  • Camille Coti
  • , Laure Petrucci
  • , César Rodríguez
  • , Marcelo Sousa
  • Université Paris 13
  • Diffblue Ltd.
  • University of Oxford

Résultats de recherche: Contribution à un journal › Article publié dans une revue, révisé par les pairs › Revue par des pairs

5 Citations (Scopus)

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 originaleAnglais
Pages (de - à)3-33
Nombre de pages31
journalFormal Methods in System Design
Volume57
Numéro de publication1
Les DOIs
étatPublié - juil. 2021
Modification externeOui

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