{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T20:44:24Z","timestamp":1763585064672,"version":"3.45.0"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,1,10]],"date-time":"2018-01-10T00:00:00Z","timestamp":1515542400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Yahoo!"},{"name":"AFOSR\/AFRL","award":["FA8750-11-2-0084"],"award-info":[{"award-number":["FA8750-11-2-0084"]}]},{"name":"Microsoft"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS 1409416, CNS 1319527 and CCF 0964471"],"award-info":[{"award-number":["CNS 1409416, CNS 1319527 and CCF 0964471"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"VMware Graduate Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2017,2,3]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2997654","type":"journal-article","created":{"date-parts":[[2017,1,10]],"date-time":"2017-01-10T10:41:17Z","timestamp":1484044877000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Characterizing and Adapting the Consistency-Latency Tradeoff in Distributed Key-Value Stores"],"prefix":"10.1145","volume":"11","author":[{"given":"Muntasir Raihan","family":"Rahman","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lewis","family":"Tseng","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Son","family":"Nguyen","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Indranil","family":"Gupta","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nitin","family":"Vaidya","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,1,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2012.33"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0139-2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2685048.2685077"},{"key":"e_1_2_1_4_1","unstructured":"K. J. Astrom and T. Hagglund. 1995. PID Controllers: Theory Design and Tuning 2nd Ed. The Instrument Systems and Automation Society Research Triangle Park NC."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/176575.176576"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2460276.2462076"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0330-1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465260"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/EDCC.2006.13"},{"key":"e_1_2_1_10_1","unstructured":"Jeff Barr. 2013. Real-time ad impression bids using DynamoDB. Retrieved from http:\/\/goo.gl\/C7gdpc."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879175"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/343477.343502"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835701"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 4th Annual Symposium on Cloud Computing (SoCC)","author":"Cockcroft Adrian","year":"2013","unstructured":"Adrian Cockcroft. 2013. Dystopia as a service (invited talk). In Proceedings of the 4th Annual Symposium on Cloud Computing (SoCC). Santa Clara, California."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_16_1","unstructured":"Brian F. Cooper Adam Silberstein Erwin Tam Raghu Ramakrishnan and Russell Sears. 2010b. Yahoo! Cloud serving benchmark (YCSB). Retrieved from http:\/\/goo.gl\/GiA5c."},{"key":"e_1_2_1_17_1","unstructured":"Brian F. Cooper Adam Silberstein Erwin Tam Raghu Ramakrishnan and Russell Sears. 2010c. Yahoo! Cloud serving benchmark (YCSB) workloads. Retrieved from https:\/\/github.com\/brianfrankcooper\/YCSB\/wiki\/Core-Workloads."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387880.2387905"},{"key":"e_1_2_1_19_1","unstructured":"DataStax. 2016. Configuring data consistency. Retrieved from https:\/\/goo.gl\/PKNUXV."},{"key":"e_1_2_1_20_1","unstructured":"Aaron Davidson Aviad Rubinstein Anirudh Todi Peter Bailis and Shivaram Venkataraman. 2013. Adaptive hybrid quorums in practical settings. Retrieved from http:\/\/goo.gl\/LbRSW3."},{"key":"e_1_2_1_21_1","unstructured":"Jeff Dean. 2009. Design Lessons and Advice from Building Large Distributed Systems. Retrieved from http:\/\/goo.gl\/HGJqUh."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJWGS.2005.007545"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/645956.675942"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752949"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/822076.822436"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.295"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/564585.564601"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2011.389"},{"key":"e_1_2_1_30_1","unstructured":"Eric Gilmore. 2011. Cassandra multi data-center deployment. Retrieved from http:\/\/goo.gl\/aA8YIS."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043559"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993834"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2014.57"},{"key":"e_1_2_1_34_1","first-page":"032","article-title":"Providing A Measure Representing an Instantaneous Data Consistency Level. (Jan. 2014)","volume":"20","author":"Golab Wojciech","year":"2014","unstructured":"Wojciech Golab and John Johnson Wylie. 2014. Providing A Measure Representing an Instantaneous Data Consistency Level. (Jan. 2014). US Patent Application 20,140,032,504.","journal-title":"US Patent Application"},{"key":"e_1_2_1_35_1","unstructured":"Andy Gross. 2009. Basho riak. Retrieved from http:\/\/basho.com\/riak\/."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/975344"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038916.2038934"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2003.1247672"},{"key":"e_1_2_1_39_1","unstructured":"Avinash Lakshman and Prashant Malik. 2008. Apache Cassandra. Retrieved from http:\/\/cassandra. apache.org\/."},{"key":"e_1_2_1_40_1","volume-title":"Amazon: Milliseconds means money.","author":"Lang Keith","year":"2009","unstructured":"Keith Lang. 2009. Amazon: Milliseconds means money. Retrieved from http:\/\/goo.gl\/fs9pZb."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/876878.879235"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387880.2387906"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00530-006-0026-0"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1809049.1809051"},{"key":"e_1_2_1_45_1","unstructured":"LinkedIn. 2009. Project Voldemort. Retrieved from http:\/\/goo.gl\/9uhLoU."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043593"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/2482626.2482657"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/259380.259458"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)90244-4"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363942"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/2482626.2482629"},{"key":"e_1_2_1_52_1","unstructured":"Ron Peled. 2010. Activo: \u201cWhy low latency matters?\u201d Retrieved from http:\/\/goo.gl\/2XQ8Ul."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741974"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the International Conference on Distributed Computing Systems (ICDCS). 198--204","author":"Shapiro Marc","year":"1986","unstructured":"Marc Shapiro. 1986. Structure and encapsulation in distributed systems: The proxy principle. In Proceedings of the International Conference on Distributed Computing Systems (ICDCS). 198--204."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/2050613.2050642"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737981"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383071"},{"key":"e_1_2_1_58_1","unstructured":"Shlomo Swidler. 2009. Consistency in Amazon S3. Retrieved from http:\/\/goo.gl\/yhAoJy."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522731"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1435417.1435432"},{"volume-title":"\u201cGood enough","author":"Wei Hengfeng","key":"e_1_2_1_61_1","unstructured":"Hengfeng Wei, Yu Huang, Jiannong Cao, and Jian Lu. 2015. Almost strong consistency: \u201cGood enough\u201d in distributed storage systems. Retrieved from http:\/\/arxiv.org\/abs\/1507.01663."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/1060289.1060313"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/566340.566342"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814576.2814733"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.5555\/850929.851952"}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2997654","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2997654","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2997654","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:22:59Z","timestamp":1763457779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2997654"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,10]]},"references-count":65,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,2,3]]}},"alternative-id":["10.1145\/2997654"],"URL":"https:\/\/doi.org\/10.1145\/2997654","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"type":"print","value":"1556-4665"},{"type":"electronic","value":"1556-4703"}],"subject":[],"published":{"date-parts":[[2017,1,10]]},"assertion":[{"value":"2015-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}