CausalSpartan: Causal Consistency for Distributed Data Stores Using Hybrid Logical Clocks
- 1 September 2017
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2017 IEEE 36th Symposium on Reliable Distributed Systems (SRDS)
- p. 184-193
- https://doi.org/10.1109/srds.2017.27
Abstract
Causal consistency is an intermediate consistency model that can be achieved together with high availability and high-performance requirements even in presence of network partitions. In the context of partitioned data stores, it has been shown that implicit dependency tracking using clocks is more efficient than explicit dependency tracking by sending dependency check messages. Existing clock-based solutions depend on monotonic psychical clocks that are closely synchronized. These requirements make current protocols vulnerable to clock anomalies. In this paper, we propose a new clock-based algorithm, CausalSpartan, that instead of physical clocks, utilizes Hybrid Logical Clocks (HLCs). We show that using HLCs, without any overhead, we make the system robust on physical clock anomalies. This improvement is more significant in the context of query amplification, where a single query results in multiple GET/PUT operations. We also show that CausalSpartan decreases the visibility latency for a given data item comparing to existing clock-based approaches. In turn, this reduces the completion time of collaborative applications where two clients accessing two different replicas edit same items of the data store. Like previous protocols, CausalSpartan assumes that a given client does not access more than one replica. We show that in presence of network partitions, this assumption (made in several other works) is essential if one were to provide causal consistency as well as immediate availability to local updates.Keywords
This publication has 11 references indexed in Scilit:
- Existential consistencyPublished by Association for Computing Machinery (ACM) ,2015
- GentleRainPublished by Association for Computing Machinery (ACM) ,2014
- Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the StoryComputer, 2012
- Eventually consistentCommunications of the ACM, 2009
- DynamoACM SIGOPS Operating Systems Review, 2007
- Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web servicesACM SIGACT News, 2002
- Flexible update propagation for weakly consistent replicationACM SIGOPS Operating Systems Review, 1997
- Causal memory: definitions, implementation, and programmingDistributed Computing, 1995
- Providing high availability using lazy replicationACM Transactions on Computer Systems, 1992
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978