DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2021.16

Dynamic Data-Race Detection Through the Fine-Grained Lens

Authors: Rucha Kulkarni, Umang Mathur, and Andreas Pavlogiannis

Published in: LIPIcs, Volume 203, 32nd International Conference on Concurrency Theory (CONCUR 2021)

Abstract

Data races are among the most common bugs in concurrency. The standard approach to data-race detection is via dynamic analyses, which work over executions of concurrent programs, instead of the program source code. The rich literature on the topic has created various notions of dynamic data races, which are known to be detected efficiently when certain parameters (e.g., number of threads) are small. However, the fine-grained complexity of all these notions of races has remained elusive, making it impossible to characterize their trade-offs between precision and efficiency. In this work we establish several fine-grained separations between many popular notions of dynamic data races. The input is an execution trace σ with 𝒩 events, 𝒯 threads and ℒ locks. Our main results are as follows. First, we show that happens-before HB races can be detected in O(𝒩⋅ min(𝒯, ℒ)) time, improving over the standard O(𝒩⋅ 𝒯) bound when ℒ = o(𝒯). Moreover, we show that even reporting an HB race that involves a read access is hard for 2-orthogonal vectors (2-OV). This is the first rigorous proof of the conjectured quadratic lower-bound in detecting HB races. Second, we show that the recently introduced synchronization-preserving races are hard to detect for 3-OV and thus have a cubic lower bound, when 𝒯 = Ω(𝒩). This establishes a complexity separation from HB races which are known to be strictly less expressive. Third, we show that lock-cover races are hard for 2-OV, and thus have a quadratic lower-bound, even when 𝒯 = 2 and ℒ = ω(log 𝒩). The similar notion of lock-set races is known to be detectable in O(𝒩⋅ ℒ) time, and thus we achieve a complexity separation between the two. Moreover, we show that lock-set races become hitting-set (HS)-hard when ℒ = Θ(𝒩), and thus also have a quadratic lower bound, when the input is sufficiently complex. To our knowledge, this is the first work that characterizes the complexity of well-established dynamic race-detection techniques, allowing for a rigorous comparison between them.

Cite as

Rucha Kulkarni, Umang Mathur, and Andreas Pavlogiannis. Dynamic Data-Race Detection Through the Fine-Grained Lens. In 32nd International Conference on Concurrency Theory (CONCUR 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 203, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kulkarni_et_al:LIPIcs.CONCUR.2021.16,
  author =	{Kulkarni, Rucha and Mathur, Umang and Pavlogiannis, Andreas},
  title =	{{Dynamic Data-Race Detection Through the Fine-Grained Lens}},
  booktitle =	{32nd International Conference on Concurrency Theory (CONCUR 2021)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-203-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{203},
  editor =	{Haddad, Serge and Varacca, Daniele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2021.16},
  URN =		{urn:nbn:de:0030-drops-143931},
  doi =		{10.4230/LIPIcs.CONCUR.2021.16},
  annote =	{Keywords: dynamic analyses, data races, fine-grained complexity}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2020.73

Smoothed Efficient Algorithms and Reductions for Network Coordination Games

Authors: Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract

We study the smoothed complexity of finding pure Nash equilibria in Network Coordination Games, a PLS-complete problem in the worst case, even when each player has two strategies. This is a potential game where the sequential-better-response algorithm is known to converge to a pure NE, albeit in exponential time. First, we prove polynomial (respectively, quasi-polynomial) smoothed complexity when the underlying game graph is complete (resp. arbitrary), and every player has constantly many strategies. The complete graph assumption is reminiscent of perturbing all parameters, a common assumption in most known polynomial smoothed complexity results. We develop techniques to bound the probability that an (adversarial) better-response sequence makes slow improvements to the potential. Our approach combines and generalizes the local-max-cut approaches of Etscheid and Röglin (SODA `14; ACM TALG, `17) and Angel, Bubeck, Peres, and Wei (STOC `17), to handle the multi-strategy case. We believe that the approach and notions developed herein could be of interest in addressing the smoothed complexity of other potential games. Further, we define a notion of a smoothness-preserving reduction among search problems, and obtain reductions from 2-strategy network coordination games to local-max-cut, and from k-strategy games (k arbitrary) to local-max-bisection. The former, with the recent result of Bibak, Chandrasekaran, and Carlson (SODA `18) gives an alternate O(n^8)-time smoothed algorithm when k=2. These reductions extend smoothed efficient algorithms from one problem to another.

Cite as

Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta. Smoothed Efficient Algorithms and Reductions for Network Coordination Games. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 73:1-73:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{boodaghians_et_al:LIPIcs.ITCS.2020.73,
  author =	{Boodaghians, Shant and Kulkarni, Rucha and Mehta, Ruta},
  title =	{{Smoothed Efficient Algorithms and Reductions for Network Coordination Games}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{73:1--73:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.73},
  URN =		{urn:nbn:de:0030-drops-117581},
  doi =		{10.4230/LIPIcs.ITCS.2020.73},
  annote =	{Keywords: Network Coordination Games, Smoothed Analysis}
}

Search Results

Documents authored by Kulkarni, Rucha

Dynamic Data-Race Detection Through the Fine-Grained Lens

Abstract

Cite as

Smoothed Efficient Algorithms and Reductions for Network Coordination Games

Abstract

Cite as

Thanks for your feedback!

Could not send message