Value the Recent Past: Approximate Causal Consistency for Partially Replicated Systems

In wide-area distributed systems, data replication provides fault tolerance and low latency. Causal consistency in such systems is an interesting consistency model. Most existing works assume the data is fully replicated because this greatly simplifies the design of the algorithms to implement causal consistency. Recently, we proposed causal consistency under partial replication because it reduces the number of messages used under a wide range of workloads. One drawback of partial replication is that its meta-data tends to be relatively large when the message size is small. In this paper, we propose an algorithm Approx-Opt-Track which provides approximate causal consistency whereby we can reduce the meta-data at the cost of some violations of causal consistency. The amount of violations can be made arbitrarily small by controlling a tunable parameter, that we call credits. We present the analytic data to show the performance of Approx-Opt-Track. We then give simulation results to show the potential benefit of Approx-Opt-Track, viz., its ability to provide almost the same guarantees as causal consistency, at a smaller cost.