Name
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 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 >= 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 . 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1137/16M1056389 | SIAM JOURNAL ON COMPUTING |
Keywords | DocType | Volume |
consistency,atomicity,verification,distributed storage | Journal | 47 |
Issue | ISSN | Citations |
2 | 0097-5397 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wojciech Golab | 1 | 210 | 17.22 |
| Xiaozhou Steve Li | 2 | 179 | 10.55 |
| Alejandro López-Ortiz | 3 | 1252 | 107.44 |
| Naomi Nishimura | 4 | 65 | 6.38 |