2018/05/25 by Duong Nguyen, Aleksey Charapko, Nguyen, Duong +7 · 1 citation
Computer Science · #Cloud Computing and Resource Management #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #Software System Performance and Reliability #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1805.11453
arXiv admin note: substantial text overlap with arXiv:1801.07319
openalex publication_date 2018/05/25 · arxiv created 2018/06/24 · arxiv updated 2018/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Limitations of the CAP theorem imply that if availability is desired in the presence of network partitions, 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 he/she has an algorithm that works correctly with sequential consistency but is faced with an underlying key-value store that provides a weaker (e.g., eventual or causal) consistency. We propose a detect-rollback 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 key-value 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 key-value store. Our experiments with deployment on Amazon AWS EC2 instances shows that using eventual consistency with monitoring can provide a 50-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.