The Complexity of Dynamic Data Race Prediction

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskning


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.

TitelLICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science
Antal sider15
UdgivelsesstedNew York
ForlagAssociation for Computing Machinery
ISBN (Elektronisk)978-1-4503-7104-9
StatusUdgivet - 2020
Begivenhed35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020 - Saarbrucken, Tyskland
Varighed: 8 jul. 202011 jul. 2020


Konference35th 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


  • Data Race Prediction, Complexity

Se relationer på Aarhus Universitet Citationsformater

ID: 195357031