Cost-Effective Protocols for Enforcing Causal Consistency in Geo-Replicated Data Store Systems

Causal consistency in geo-replicated systems is an interesting consistency model. Most existing works with causal consistency have focused on the full replication for the data. This greatly simplifies the design of the algorithms to implement causal consistency. This is because full replication protocols do not need to track transitive causal dependencies between each pair of processes. However, partial replication protocols have several advantages, such as each write/update operation leads to fewer messages being multicast and smaller storage overheads. Although partial replication can avoid unnecessary network traffic and prevent decreased responsiveness, it poses big challenges to realize partial replication against full replication. This is primarily due to the higher complexity of tracking causal consistency, resulting in additional communication cost and larger dependency meta-data overheads. In this dissertation, we propose an optimal partial replication protocol-Opt-Track-for causal consistency and give a special case algorithm-Opt-Track-CRP-for causal consistency in the full-replication case, in distributed key-value data store systems. Next, 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. Then, we address the problem of determining suitable replica placement on-the-fly to increase the availability of data resources and maximize the system utilization. We propose Cost Optimization Replica Placement (CORP) algorithms to enable state-of-art proactive provisioning of data resources based on an one-step look-ahead workload behavior pattern forecast over the distributed data storage infrastructure using statistical techniques. Furthermore, we propose a causal+ consistency protocol, CaDRoP(+cache), to support dynamic replication, to ensure the convergence property for all comments following a post, and to enforce the causal ordering between posts with explicit causality.