Causal Consistency Algorithms for Partially Replicated and Fully Replicated Systems

Data replication is commonly used for fault-tolerance in reliable distributed systems. In large-scale systems, it additionally provides low latency. Recently, in the context of distributed shared memory systems and geo-replicated cloud storage, causal consistency has received much attention. However, existing works assume the data is fully replicated. This greatly simplifies the design of the algorithms to implement causal consistency. In this work, we propose that it can be advantageous to have partial replication of data, and we propose two algorithms for achieving causal consistency in such systems where the data is only partially replicated. We also give a special case algorithm for causal consistency in the full-replication case. We give simulation results to show the performance of our algorithms, and to present the advantage of partial replication over full replication.

Bio: Ajay Kshemkalyani is currently a professor in the Department of Computer Science at the University of Illinois at Chicago. He holds a PhD in Computer Science from The Ohio State University. His research interests are in distributed computing, distributed algorithms, computer networks, and concurrent systems. In 1999, he received the US National Science Foundation Career Award. He has served on the editorial board of the Elsevier journal Computer Networks, and the IEEE Transactions on Parallel and Distributed Systems. He has coauthored a book entitled Distributed Computing: Principles, Algorithms, and Systems (Cambridge University Press, 2011).