Aarhus University Seal

The Complexity of Dynamic Data Race Prediction

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


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 data-race 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 · n2·(k-1) upper-bound, as well as an O(nk) 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(k2 · d · n2 · 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(n2-) algorithm under the Orthogonal Vectors conjecture. Since any trace with 2 threads defines an acyclic topology, our upper-bound for this case is optimal up to 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.

Original languageEnglish
Title of host publicationProceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020
Number of pages15
Place of publicationNew York
PublisherAssociation for Computing Machinery
Publication year8 Jul 2020
Article number3394783
ISBN (Electronic)978-1-4503-7104-9
Publication statusPublished - 8 Jul 2020
Event35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020 - Saarbrucken, Germany
Duration: 8 Jul 202011 Jul 2020


Conference35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020
SponsorACM Special Interest Group on Logic and Computation (SIGLOG), Association for Symbolic Logic, European Association for Theoretical Computer Science (EATCS), IEEE Technical Committee on Mathematical Foundations of Computing

Bibliographical note

Publisher Copyright:
© 2020 ACM.

Copyright 2020 Elsevier B.V., All rights reserved.

    Research areas

  • Complexity, Data Race Prediction

See relations at Aarhus University Citationformats

ID: 195357031