Achieving convergent causal consistency and high availability for cloud storage

The tradeoff between consistency and availability is inevitable when designing distributed data stores, and today's cloud services often choose high availability instead of strong consistency, leading to visible inconsistencies for clients. Convergent causal consistency is one of the strongest consistency model that still remains available during system partitions, and it can also satisfy human perception of causality between events. In this paper, we present CoCaCo, a distributed key-value store that provides convergent causal consistency with asynchronous replication, since it is able to provide cloud services' desired properties including high performance and availability. Moreover, CoCaCo can efficiently guarantee causal consistency by performing dependency checking only during handling read operations. We implement CoCaCo based on Cassandra and our experimental results indicate that CoCaCo provides performance comparable to eventually consistent Cassandra.