English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Data races are among the most common bugs in concurrency. The standardapproach to data-race detection is via dynamic analyses, which work overexecutions of concurrent programs, instead of the program source code. The richliterature 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 \emph{fine-grained} complexity ofall these notions of races has remained elusive, making it impossible tocharacterize their trade-offs between precision and efficiency.  In this work we establish several fine-grained separations between manypopular notions of dynamic data races. The input is an execution trace with $N$events, $T$ threads and $L$ locks. Our main results are as follows. First, weshow that happens-before (HB) races can be detected in $O(N\cdot \min(T, L))$time, improving over the standard $O(N\cdot T)$ bound when $L=o(T)$. Moreover,we show that even reporting an HB race that involves a read access is hard for2-orthogonal vectors (2-OV). This is the first rigorous proof of theconjectured quadratic lower-bound in detecting HB races. Second, we show thatthe recently introduced synchronization-preserving races are hard to detect forOV-3 and thus have a cubic lower bound, when $T=\Omega(N)$. This establishes acomplexity separation from HB races which are known to be less expressive.Third, we show that lock-cover races are hard for 2-OV, and thus have aquadratic lower-bound, even when $T=2$ and $L = \omega(\log N)$. The similarnotion of lock-set races is known to be detectable in $O(N\cdot L)$ time, andthus we achieve a complexity separation between the two. Moreover, we show thatlock-set races become hitting-set (HS)-hard when $L=\Theta(N)$, and thus alsohave a quadratic lower bound, when the input is sufficiently complex.

Dynamic Data-Race Detection through the Fine-Grained Lens