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_16: Cloud storage services and NoSQL systems, which have recently found widespread adoption, typically offer only "Eventual Consistency", a rather weak guarantee covering a broad range of potential data consistency behavior. The degree of actual (in-)consistency as a service quality, however, is always unknown. To avoid cost of opportunity or actual costs, resulting data inconsistencies have to be resolved within the application layer. Without detailed knowledge on consistency behavior, though, inconsistency handling is inefficient and for some kinds of inconsistency outright impossible. Furthermore, due to the way consistency behavior impacts applications, consistency as a system quality should also be considered during the selection and deployment optimization of cloud storage offerings and NoSQL systems. This as well as studying the impact of system design decisions on consistency behavior requires the necessary means to analyze consistency behavior of eventually consistent storage systems. In this work, we present four main contributions to address the problems outlined above: First, we develop novel consistency metrics which describe consistency behavior for all kinds of consistency, in a precise way, without needless aggregation, and in way that is meaningful to application or storage system developers as well as systems researchers. Second, we identify key influence factors on consistency behavior and combine them into a model of a storage system. We then present two distinct approaches, which predict consistency behavior based on simulations on top of this model. Third, we also present a set of system benchmarking approaches to accurately determine consistency behavior of eventually consistent distributed storage systems via experiments with actually deployed systems. Results of both simulation and system benchmarking are expressed using our novel set of consistency metrics. Fourth, building on 15 extensive experiments with actual systems and a multitude of simulation runs, we demonstrate how inconsistencies can be handled more efficiently leveraging these results. For this purpose, we describe based on a use case how inconsistencies can be resolved in application engineering. We also develop a new middleware-based approach which adds additional consistency guarantees externally to the eventually consistent storage system, thus, alleviating complexity for application developers.
@cite_10: Reliability at massive scale is one of the biggest challenges we face at Amazon.com, one of the largest e-commerce operations in the world; even the slightest outage has significant financial consequences and impacts customer trust. The Amazon.com platform, which provides services for many web sites worldwide, is implemented on top of an infrastructure of tens of thousands of servers and network components located in many datacenters around the world. At this scale, small and large components fail continuously and the way persistent state is managed in the face of these failures drives the reliability and scalability of the software systems. This paper presents the design and implementation of Dynamo, a highly available key-value storage system that some of Amazon's core services use to provide an "always-on" experience. To achieve this level of availability, Dynamo sacrifices consistency under certain failure scenarios. It makes extensive use of object versioning and application-assisted conflict resolution in a manner that provides a novel interface for developers to use.
@cite_22: 
@cite_6: The traditional assumption about memory is that a read returns the value written by the most recent write. However, in a shared memory multiprocessor several processes independently and simultaneously submit reads and writes resulting in a partial order of memory operations. In this partial order, the definition of most recent write may be ambiguous. Memory consistency models have been developed to specify what values may be returned by a read given that memory operations may only be partially ordered. Before this work, consistency models were defined independently. Each model followed a set of rules which was separate from the rules of every other model. In our work, we have defined a set of four consistency properties. Any subset of the four properties yields a set of rules which constitute a consistency model. Every consistency model previously described in the literature can be defined based on our four properties. Therefore, we present these properties as a unfied theory of shared memory consistency.Our unified theory provides several benefits. First, we claim that these four properties capture the underlying structure of memory consistency. That is, the goal of memory consistency is to ensure certain declarative properties which can be intuitively understood by a programmer, and hence allow him or her to write a correct program. Our unified theory provides a uniform, formal definition of all previously described consistency models, and in addition some combinations of properties produce new models that have not yet been described. We believe these new models will prove to be useful because they are based on declarative properties which programmers desire to be enforced. Finally, we introduce the idea of selecting a consistency model as an on-line activity. Before our work, a shared memory program would run start to finish under a single consistency model. Our unified theory allows the consistency model to change as the program runs while maintaining a consistent definition of what values may be returned by each read.
Distributed storage systems emphasize the paramount importance of high availability and resilience to failures @cite_10 @cite_22 . Thus eventual consistency is often adopted @cite_16 . The notion of eventual consistency is promoted by practitioners. It is different from the rigorous and formal treatment of consistency models in the academia @cite_6 .