Characterizing and adapting the consistency-latency tradeoff in distributed key-value stores

Muntasir Raihan Rahman, Lewis Tseng, Son Nguyen, Indranil Gupta, Nitin Vaidya

Research output: Contribution to journalArticlepeer-review


The CAP theorem is a fundamental result that applies to distributed storage systems. In this article, we first present and prove two CAP-like impossibility theorems. To state these theorems, we present probabilistic models to characterize the three important elements of the CAP theorem: consistency (C), availability or latency (A), and partition tolerance (P). The theorems show the un-achievable envelope, that is, which combinations of the parameters of the three models make them impossible to achieve together. Next, we present the design of a class of systems called Probabilistic CAP (PCAP) that perform close to the envelope described by our theorems. In addition, these systems allow applications running on a single data center to specify either a latency Service Level Agreement (SLA) or a consistency SLA. The PCAP systems automatically adapt, in real time and under changing network conditions, to meet the SLA while optimizing the other C/A metric. We incorporate PCAP into two popular key-value stores: Apache Cassandra and Riak. Our experiments with these two deployments, under realistic workloads, reveal that the PCAP systems satisfactorily meets SLAs and perform close to the achievable envelope. We also extend PCAP from a single data center to multiple geo-distributed data centers.

Original languageEnglish (US)
Article number20
JournalACM Transactions on Autonomous and Adaptive Systems
Issue number4
StatePublished - Jan 2017


  • Adaptivity
  • Consistency
  • Distributed storage

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science (miscellaneous)
  • Software


Dive into the research topics of 'Characterizing and adapting the consistency-latency tradeoff in distributed key-value stores'. Together they form a unique fingerprint.

Cite this