## 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 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 language | English |
---|---|

Title of host publication | Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020 |

Number of pages | 15 |

Place of publication | New York |

Publisher | Association for Computing Machinery |

Publication date | 8 Jul 2020 |

Pages | 713–727 |

Article number | 3394783 |

ISBN (Electronic) | 978-1-4503-7104-9 |

DOIs | |

Publication status | Published - 8 Jul 2020 |

Event | 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020 - Saarbrucken, Germany Duration: 8 Jul 2020 → 11 Jul 2020 |

### Conference

Conference | 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020 |
---|---|

Country/Territory | Germany |

City | Saarbrucken |

Period | 08/07/2020 → 11/07/2020 |

## Keywords

- Complexity
- Data Race Prediction