Comparing Causal Convergence Consistency Models

In distributed databases, the CAP theorem establishes that a distributed storage system can only ensure two out of three properties: strong data consistency (i.e., reads returning the most recent writes), availability, or partition tolerance. Modern distributed storage systems prioritize performance and availability over strong consistency and thus offer weaker consistency models such as causal consistency. This paper explores several variations of causal consistency (CC) that guarantee state convergence among replicas, meaning that all distributed replicas converge towards the same consistent state. We investigate a log-based CC model, a commutativity-based CC model, and a global sequence protocol-based CC model. To facilitate our study of the relationships between these models, we use a common formalism to define them. We then show that the log-based CC model is the weakest, while the commutativity-based CC and the global sequence protocol-based CC models are incomparable. We also provide sufficient conditions for a given application program to be robust against one CC model versus another, meaning that the program has the same behavior when executed over databases implementing the two CC models.