Distributed key-value stores have become a de facto component of modern web-scale applications. These data stores provide low latency operations to clients across the world. Many of these data stores support eventual consistency, which is the weakest form of consistency and offers the best performance. However, eventual consistency does not provide any practically useful guarantees, except that once there are no new updates to a data item, it will eventually become consistent. Causal consistency, on the other hand, has caught up attention in recent years, as it lies in between the two extremes of eventual consistency and strong consistency. It is also the strongest form of consistency that can satisfy all the three properties of the CAP theorem, which makes it a good candidate for distributed applications.



In the past few years, various protocols for enforcing causal consistency have been proposed. A majority of these protocols focus on optimizing read operations since real-world workloads are often read-heavy. In particular, most protocols support Read Only Transactions (ROT), which allows a client to read multiple keys from a causally consistent snapshot. In this work, we present a novel ROT protocol, named Orion, to reduce communication in the underlying distributed network. A salient feature of Orion is that it uses only one round of communication in the best case, unlike the usual, fixed two rounds in other protocols. Reduction in rounds is achieved by carefully predicting the stable vector of data items. We provide a theoretical bound on its communication complexity and qualitatively compare it with recent ROT protocols. We also quantitatively compare Orion with state-of-the-art protocol CausalSpartanX and illustrate that Orion achieves up to 1.7× higher throughput and generates 10× fewer messages on widely-used YCSB workload.