Computing weak consistency in polynomial time
Venue
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, ACM, New York, NY, USA, pp. 395-404
Publication Year
2015
Authors
Wojciech Golab, Xiaozhou (Steve) Li, Alejandro López-Ortiz, Naomi Nishimura
BibTeX
Abstract
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 Lamport's atomicity 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 >= 2
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 (k log k) time. 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.
