Resilient Distributed Causal Memory in ClientServer Model We study distributed causal shared memory (or keyvalue pairs) in an asynchronous network under crash failures. Causal memory, introduced by Ahamad et al. in the context of multiprocessor environment in 1994, is an abstraction which ensures that nodes agree on the relative ordering of read and write operations that are causally related on keyvalue pairs. Inspired by the recent interests in georeplicated causal storage systems (e.g., COPS, Eiger, Bolton), we systematically study the faulttolerance property of the causal shared memory in the clientserver model in this work. We identify that 2f  1 servers is both necessary and sufficient to build a resilient causal memory in the presence of up to f crashed servers. We provide both the necessity proof and a new optimal algorithm that matches the bound. For evaluation, we implement our algorithm in Golang and compare the performance with stateoftheart faulttolerant algorithms that ensure strong consistency in the Google Cloud Platform.

Using Weaker Consistency Models with Monitoring and Recovery for Improving Performance of KeyValue Stores Limitations of the CAP theorem imply that if availability is desired in the presence of faults xe2x80x93 especially that create network partitions (or substantial delays), one must sacrifice sequential consistency, a consistency model that is more natural for system design. We focus on the problem of what a designer should do if heshe has an algorithm that works correctly with sequential consistency but is faced with an underlying keyvalue store that provides a weaker (e.g., eventual or causal) consistency. We propose a detectrollback based approach: The designer identifies a correctness predicate, say P, and continues to run the protocol, as our system monitors P. If P is violated (because the underlying keyvalue store provides a weaker consistency), the system rolls back and resumes the computation at a state where P holds. We evaluate this approach with practical graph applications running on the Voldemort keyvalue store. Our experiments, deployed on Amazon AWS EC2 instances, show that using eventual consistency with monitoring can provide a 50 xe2x80x93 80% increase in throughput when compared with sequential consistency. We also show that the overhead of the monitoring itself is low (typically less than 4%) and the latency of detecting violations is small. In particular, more than 99.9% of violations are detected in less than 50 milliseconds in regional AWS networks, and in less than 5 seconds in global AWS networks. In turn, this makes it possible to provide efficient recovery from such faults with a minimal amount of work wasted due to rollbacks.