Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning

- https://doi.org/10.1145/3373718.3394783
Forlagets udgivne version

- Umang Mathur ,
- Andreas Pavlogiannis
- Mahesh Viswanathan

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.

Originalsprog | Engelsk |
---|---|

Titel | LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science |

Antal sider | 15 |

Udgivelsessted | New York |

Forlag | Association for Computing Machinery |

Udgivelsesår | 2020 |

Sider | 713–727 |

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

DOI | |

Status | Udgivet - 2020 |

Begivenhed | 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020 - Saarbrucken, Tyskland Varighed: 8 jul. 2020 → 11 jul. 2020 |

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

Land | Tyskland |

By | Saarbrucken |

Periode | 08/07/2020 → 11/07/2020 |

Sponsor | ACM 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