Lune

LICS2020Top-tier venue

The Complexity of Dynamic Data Race Prediction

Umang Mathur, Andreas Pavlogiannis, Mahesh Viswanathan

Abstract

Writing concurrent programs is notoriously hard due to scheduling non-determinism. The most common concurrency bugs are data races, which are accesses to a shared resource that can be executed concurrently. Dynamic datarace prediction is the most standard technique for detecting data races: given an observed, data-race-free trace t, the task is to determine whether t can be reordered to a trace t * that exposes a data-race. Although the problem has received significant practical attention for over three decades, its complexity has remained elusive. In this work, we address this lacuna, identifying sources of intractability and conditions under which the problem is efficiently solvable. Given a trace t of size n over k threads, our main results are as follows.

First, we establish a general O(k • n 2•(k-1) ) upper-bound, as well as an O(n k ) upper-bound when certain parameters of t are constant. In addition, we show that the problem is NP-hard and even W[1]-hard parameterized by k, and thus unlikely to be fixed-parameter tractable. Second, we study the problem over acyclic communication topologies, such as server-clients hierarchies. We establish an O(k 2 •d •n 2 • log n) upper-bound, where d is the number of shared variables accessed in t. In addition, we show that even for traces with k = 2 threads, the problem has no O(n 2-ϵ ) algorithm under the Orthogonal Vectors conjecture. Since any trace with 2 threads defines an acyclic topology, our upper-bound for this case is optimal wrt polynomial improvements for up to moderate values of k and d. Finally, motivated by existing heuristics, we study a distance-bounded version of the problem, where the task is to expose a data race by a witness trace that is similar to t. We develop an algorithm that works in O(n) time when certain parameters of t are constant.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

22 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Sound Dynamic Deadlock Prediction in Linear Time cites Fast, sound, and effectively complete dynamic race prediction
  • Sound Dynamic Deadlock Prediction in Linear Time cites Optimal prediction of synchronization-preserving races
  • The reads-from equivalence for the TSO and PSO memory models cites Fast, sound, and effectively complete dynamic race prediction
  • Predictive Monitoring against Pattern Regular Languages cites Sound Dynamic Deadlock Prediction in Linear Time
  • Predictive Monitoring against Pattern Regular Languages cites Fast, sound, and effectively complete dynamic race prediction
  • Predictive Monitoring against Pattern Regular Languages cites Optimal prediction of synchronization-preserving races
  • Optimal Reads-From Consistency Checking for C11-Style Memory Models cites Fast, sound, and effectively complete dynamic race prediction
  • Optimal Reads-From Consistency Checking for C11-Style Memory Models cites The reads-from equivalence for the TSO and PSO memory models
  • Optimal Reads-From Consistency Checking for C11-Style Memory Models cites Optimal prediction of synchronization-preserving races
  • Optimal prediction of synchronization-preserving races cites Fast, sound, and effectively complete dynamic race prediction
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers22

  1. Optimal prediction of synchronization-preserving racesUmang Mathur, Andreas Pavlogiannis, Mahesh ViswanathanPOPL 2021 · 36 citations
  2. Sound Dynamic Deadlock Prediction in Linear TimeHünkar Can Tunç, Umang Mathur, Andreas Pavlogiannis, Mahesh ViswanathanPLDI 2023 · 15 citations
  3. The reads-from equivalence for the TSO and PSO memory modelsTruc Lam Bui, Krishnendu Chatterjee, Tushar Gautam, Andreas Pavlogiannis et al.OOPSLA 2021 · 13 citations
  4. Predictive Monitoring against Pattern Regular LanguagesZhendong Ang, Umang MathurPOPL 2024 · 12 citations
  5. Optimal Reads-From Consistency Checking for C11-Style Memory ModelsHünkar Can Tunç, Parosh Aziz Abdulla, Soham Chakraborty, Shankaranarayanan Krishna et al.PLDI 2023 · 12 citations

Builds on1

  1. Fast, sound, and effectively complete dynamic race predictionAndreas PavlogiannisPOPL 2020 · 46 citations

Related papers

  1. Optimistic Prediction of Synchronization-Reversal Data RacesZheng Shi, Umang Mathur, Andreas PavlogiannisICSE 2024 · 8 citations
  2. Tolerate Control-Flow Changes for Sound Data Race PredictionShihao Zhu, Yuqi Guo, Long Zhang, Yan CaiICSE 2023 · 5 citations
  3. Accurate Static Data Race Detection for CEmerson Sales, Omar Inverso, Emilio TuostoFM 2024 · 1 citation
  4. Reduce Dependence for Sound Concurrency Bug PredictionShihao Zhu, Yuqi Guo, Yan Cai, Bin Liang et al.ICSE 2025 · 1 citation
  5. Detecting concurrency vulnerabilities based on partial orders of memory and thread eventsKunpeng Yu, Chenxu Wang, Yan Cai, Xiapu Luo et al.FSE 2021 · 9 citations
Dusk over the sea between two cliffs drawn in fine vertical lines