RECOMMENDED FOR ACCEPTANCE

Geo-replicated, distributed data stores that support complex online applications, such as social networks, strive to provide an always-on experience where operations always successfully complete with low latency. Today’s systems sacrifice strong consistency and expressive semantics to achieve these goals, exposing inconsistencies to their clients and necessitating complex application logic. In this work, we identify and define a consistency model—causal consistency with convergent conflict handling, or causal+—that is the strongest achieved under these constraints. We explore the ramifications of and implementation techniques for causal+ consistency through the design and implementation of two storage systems, COPS and Eiger. COPS is a key-value store that provides causal+ consistency. A key contribution of COPS is its scalability, which can enforce causal dependencies between keys stored across an entire cluster, rather than a single server like previous systems. Eiger is a system that provides causal+ consistency for the rich column-family data model. The central approach in COPS and Eiger is tracking and explicitly checking that causal dependencies between keys are satisfied in the local cluster before exposing writes