Complexity of Consistency Testing for the Release-Acquire Semantics

Abstract In a seminal work, Gibbons and Korach [9] studied the complexity of deciding whether an observed sequence of reads and writes of a multi-threaded program admits a sequentially consistent interleaving. They showed the problem to be $\textsf{NP}$ NP -hard even under strong syntactic restrictions. More recently, Chakraborty et al. [6] considered the problem for weak memory models and proved that $\textsf{NP}$ NP -hardness remains even when the number of threads, the number of memory locations, and the value domain are all bounded. In this paper we revisit the problem for the release-acquire variants of the C11 memory model. Our main positive result is that consistency testing can be done in polynomial-time when each memory location is written by at most one thread (multiple readers are allowed). Notably, this restriction is already $\textsf{NP}$ NP -hard for the model of sequential consistency. We complement our upper bound with tight hardness results: we show the problem to be $\textsf{NP}$ NP -hard when two threads may write to the same location; furthermore, allowing three writers per location rules out $2^{o(k)}\cdot n^{\mathcal {O}(1)}$ 2 o ( k ) · n O ( 1 ) algorithms under the Exponential Time Hypothesis, where k denotes the number of threads, and n the number of memory operations.