Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Optimal Prediction of Synchronization-Preserving Races   Concurrent programs are notoriously hard to write correctly, as scheduling
nondeterminism introduces subtle errors that are both hard to detect and to
reproduce. The most common concurrency errors are (data) races, which occur
when memory-conflicting actions are executed concurrently. Consequently,
considerable effort has been made towards developing efficient techniques for
race detection. The most common approach is dynamic race prediction: given an
observed, race-free trace $\sigma$ of a concurrent program, the task is to
decide whether events of $\sigma$ can be correctly reordered to a trace
$\sigma^*$ that witnesses a race hidden in $\sigma$.
  In this work we introduce the notion of sync(hronization)-preserving races. A
sync-preserving race occurs in $\sigma$ when there is a witness $\sigma^*$ in
which synchronization operations (e.g., acquisition and release of locks)
appear in the same order as in $\sigma$. This is a broad definition that
strictly subsumes the famous notion of happens-before races. Our main results
are as follows. First, we develop a sound and complete algorithm for predicting
sync-preserving races. For moderate values of parameters like the number of
threads, the algorithm runs in $\widetilde{O}(\mathcal{N})$ time and space,
where $\mathcal{N}$ is the length of the trace $\sigma$. Second, we show that
the problem has a $\Omega(\mathcal{N}/\log^2 \mathcal{N})$ space lower bound,
and thus our algorithm is essentially time and space optimal. Third, we show
that predicting races with even just a single reversal of two sync operations
is $\operatorname{NP}$-complete and even $\operatorname{W}[1]$-hard when
parameterized by the number of threads. Thus, sync-preservation characterizes
exactly the tractability boundary of race prediction, and our algorithm is
nearly optimal for the tractable side.

17
The categories of this paper are: q-fin
11
The categories of this paper are: hep-lat
19
The categories of this paper are: eess
25
The categories of this paper are: patt-sol
13
The categories of this paper are: quant-ph
24
The categories of this paper are: dg-ga
35
The categories of this paper are: mtrl-th
12
The categories of this paper are: nucl-th
6
The categories of this paper are: astro-ph
28
The categories of this paper are: alg-geom
36
The categories of this paper are: cmp-lg
2
The categories of this paper are: math
16
The categories of this paper are: stat
33
The categories of this paper are: plasm-ph
37
The categories of this paper are: supr-con
34
The categories of this paper are: chem-ph