Skip to main navigation Skip to search Skip to main content

Quasi-optimal partial order reduction

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

Research output: Contribution to journal › Journal Article › peer-review

5 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)3-33
Number of pages31
JournalFormal Methods in System Design
Volume57
Issue number1
DOIs
Publication statusPublished - Jul 2021
Externally publishedYes

Keywords

  • Dynamic analysis
  • Non-interleaving semantics
  • Partial-order reduction
  • Program analysis

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Quasi-optimal partial order reduction'. These topics are generated from the title and abstract of the publication. Together, they form a unique fingerprint.

Cite this