  Causal consistency is an intermediate consistency model that can be achieved
together with high availability and performance requirements even in presence
of network partitions. In the context of partitioned data stores, it has been
shown that implicit dependency tracking using timestamps is more efficient than
explicit dependency tracking. Existing time-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
time-based algorithm, CausalSpartanX, 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 CausalSpartanX decreases the
visibility latency for a given data item compared with existing time-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. CausalSpartanX also provides causally consistent distributed
read-only transactions. CausalSpartanX read-only transactions are non-blocking
and require only one round of communication between the client and the servers.
Also, the slowdowns of partitions that are unrelated to a transaction do not
affect the performance of the transaction. Like previous protocols,
CausalSpartanX 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.
