Computing $k$-Atomicity in Polynomial Time
Wojciech Golab, Xiaozhou Steve, Alejandro López-Ortíz, Naomi Nishimura · SIAM Journal on Computing · 2018
The $k$-atomicity property can be used to describe the consistency of data operations in large distributed storage systems. The weak consistency guarantees offered by such systems are seen as a necessary compromise in view of Brewer's CAP principle. The $k$-atomicity property requires that every read operation obtains a value that is at most $k$ updates (writes) old and becomes a useful way to quantify weak consistency if $k$ is treated as a variable that can be computed from a history of operations. Specifically, the value of $k$ quantifies how far the history deviates from the atomicity (linearizability) property for read/write registers. We address the problem of computing $k$ indirectly by solving the $k$-atomicity verification problem ($k$-AV): given a history of read/write operations and a positive integer $k$, decide whether the history is $k$-atomic. Gibbons and Korach showed that in general this problem is NP-complete when $k=1$ and hence not solvable in polynomial time unless $P = NP$. In this paper we present two algorithms that solve the $k$-AV problem for any $k \geq 3$ in special cases. Similarly to known solutions for $k = 1$ and $k = 2$, both algorithms assume that all the values written to a given object are distinct. The first algorithm places an additional restriction on the structure of the input history and solves $k$-AV in $O(n^2 + n \cdot k \log k)$ time, where $n$ is the number of operations in the history. The second algorithm does not place any additional restrictions on the input but is efficient only when $k$ is small and when concurrency among write operations is limited. Its time complexity is $O(n^2)$ if both $k$ and our particular measure of write concurrency are bounded by constants.