CC-Paxos: Integrating Consistency and Reliability in Wide-Area Storage Systems

Data replication is widely used in geo-distributed storage systems, and strong consistency is preferred for correctness and programming simplicity at the application layer. To address the inefficiency and insufficiency of the causal consistency model, a strong consistency model named distributed context consistency is defined. It explicitly defines the necessary dependencies among distributed clients to effectively reduce falsepositive dependencies among operations. A consensus algorithm named CC-Paxos is proposed to implement this distributed context consistency model. It exploits timestamps for operation sequencing in distributed contexts and adopts fine-granularity dependency checking to effectively reduce the number of potential conflicts. Experimental results show that, compared with implementations using causal+ consistency model in the upper layer and Egalitarian Paxos in system layer, CC-Paxos can significantly decreases latency and increases throughput with no sacrifice on scalability.