Probabilistic CAP and Adaptivity in Distributed Key-value Stores

Indranil Gupta (University of Illinois at Urbana-Champaign)

Abstract: The CAP theorem is a well-known impossibility in distributed storage systems and has spurred the NoSQL revolution. In this work, we first present a generalization of the CAP theorem for distributed storage systems; this generalization is probabilistic in nature. We then show how to incorporate support for Service Level Agreements (SLAs) that take both availability and consistency into account, into today's NoSQL storage systems. Our experiments with Apache Cassandra and Riak investigate how close the performance of our adaptive SLA-based system is, compared to the bounds of our new CAP theorem.

Bio: Indranil Gupta is an Associate Professor of Computer Science at University of Illinois at Urbana-Champaign. He works on large-scale distributed systems and cloud computing systems. He has worked at Google, Microsoft Research, and IBM Research. He is also teaching a MOOC course (on Coursera) on Cloud Computing Concepts, covering distributed computing concepts used in clouds.