Both providers and consumers of distributed storage services benefit from the quantification of the severity of consistency violations. However, existing methods fail to capture a typical pattern of violation - the disorder among operations with reference to the ideally strong atomic execution. Such disorder are often seen in Internet applications based on distributed storage services, such as instant messaging. To this end, we use inversions in a permutation with reference to the totally-ordered permutation to measure the consistency of data. The @math -atomicity model is proposed and a (pseudo-)polynomial verification algorithm for a restricted type of histories is proposed. The basic idea of the verification algorithm is brute-force search of the permutation with less than @math inversions, which requires exponential cost. Reasonable assumptions abstracted from applications scenarios can be leveraged to prune the search space, which yields an efficient polynomial verification algorithm.
@cite_9: Sequential consistency is the most widely used correctness condition for multiprocessor memory systems. This paper studies the problem of testing shared-memory multiprocessors to determine if they are indeed providing a sequentially consistent memory. It presents the first formal study of this problem, which has applications to testing new memory system designs and realizations, providing run-time fault tolerance, and detecting bugs in parallel programs. A series of results are presented for testing an execution of a shared memory under various scenarios, comparing sequential consistency with linearizability, another well-known correctness condition. Linearizability imposes additional restrictions on the shared memory, beyond that of sequential consistency; these restrictions are shown to be useful in testing such memories.
@cite_15: Eventually consistent storage systems give up the ACID semantics of conventional databases in order to gain better scalability, higher availability, and lower latency. A side-effect of this design decision is that application developers must deal with stale or out of order data. As a result, substantial intellectual effort has been devoted to studying the behavior of eventually consistent systems, in particular finding quantitative answers to the questions "how eventual" and "how consistent"?
Both @math -AV and @math -AV are NP-Complete in the general case, since they include the verification of atomicity as its special case. Read-mapping is used to circumvent the NP-Completeness of atomicity verification @cite_9 . Assuming read-mapping, the @math case for @math -AV is solved in @cite_15 . For @math , the @math -AV problem is solved only for special cases. Similarly, we also assume the existence of read-mapping, and solve the @math -AV problem for a restricted type of histories. For fixed @math and @math , the problem of proving NP-Completeness for @math -AV and @math -AV for are principally open.