On the k-Atomicity-Verification Problem
Data consistency is an important consideration in storage systems. Modern Internet-scale storage systems often provide weak (rather than strong) consistency in exchange for better performance and resilience. An important weak consistency property is k-atomicity. A history of operations is called k-atomic iff there exists a valid total order on the operations (i.e., one that conforms to the partial order imposed by the operation time intervals) such that every read obtains one of the k freshest values with respect to that total order. By this definition, the well-known atomicity/linearizability is equivalent to 1-atomicity.