{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T20:44:13Z","timestamp":1763585053964},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,4]]},"abstract":"<jats:p>Data store replication results in a fundamental trade-off between operation latency and data consistency. In this paper, we examine this trade-off in the context of quorum-replicated data stores. Under partial, or non-strict quorum replication, a data store waits for responses from a subset of replicas before answering a query, without guaranteeing that read and write replica sets intersect. As deployed in practice, these configurations provide only basic eventual consistency guarantees, with no limit to the recency of data returned. However, anecdotally, partial quorums are often \"good enough\" for practitioners given their latency benefits. In this work, we explain why partial quorums are regularly acceptable in practice, analyzing both the staleness of data they return and the latency benefits they offer. We introduce Probabilistically Bounded Staleness (PBS) consistency, which provides expected bounds on staleness with respect to both versions and wall clock time. We derive a closed-form solution for versioned staleness as well as model real-time staleness for representative Dynamo-style systems under internet-scale production workloads. Using PBS, we measure the latency-consistency trade-off for partial quorum systems. We quantitatively demonstrate how eventually consistent systems frequently return consistent data within tens of milliseconds while offering significant latency benefits.<\/jats:p>","DOI":"10.14778\/2212351.2212359","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"776-787","source":"Crossref","is-referenced-by-count":111,"title":["Probabilistically bounded staleness for practical partial quorums"],"prefix":"10.14778","volume":"5","author":[{"given":"Peter","family":"Bailis","sequence":"first","affiliation":[{"name":"University of California, Berkeley"}]},{"given":"Shivaram","family":"Venkataraman","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}]},{"given":"Michael J.","family":"Franklin","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}]},{"given":"Joseph M.","family":"Hellerstein","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}]},{"given":"Ion","family":"Stoica","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}]}],"member":"320","published-online":{"date-parts":[[2012,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apache Cassandra 1.0 documentation: About data consistency in Cassandra. http:\/\/datastax.com\/docs\/1.0\/dml\/data_consistency.  Apache Cassandra 1.0 documentation: About data consistency in Cassandra. http:\/\/datastax.com\/docs\/1.0\/dml\/data_consistency."},{"key":"e_1_2_1_2_1","unstructured":"Apache Cassandra Jira: \"Support session (read-after-write) consistency\". https:\/\/issues.apache.org\/jira\/browse\/CASSANDRA-876. October 2010 (Accessed 13 December 2011).  Apache Cassandra Jira: \"Support session (read-after-write) consistency\". https:\/\/issues.apache.org\/jira\/browse\/CASSANDRA-876. October 2010 (Accessed 13 December 2011)."},{"key":"e_1_2_1_3_1","unstructured":"Basho Riak. http:\/\/basho.com\/products\/riak-overview\/(2012).  Basho Riak. http:\/\/basho.com\/products\/riak-overview\/(2012)."},{"key":"e_1_2_1_4_1","unstructured":"Cassandra 1.0 Thrift Configuration. https:\/\/github.com\/apache\/cassandra\/blob\/cassandra-1.0\/interface\/cassandra.thrift.  Cassandra 1.0 Thrift Configuration. https:\/\/github.com\/apache\/cassandra\/blob\/cassandra-1.0\/interface\/cassandra.thrift."},{"key":"e_1_2_1_5_1","unstructured":"Cassandra wiki: Operations. http:\/\/wiki.apache.org\/cassandra\/Operations#Repairing_missing_or_inconsistent_data. Accessed 13 December 2011.  Cassandra wiki: Operations. http:\/\/wiki.apache.org\/cassandra\/Operations#Repairing_missing_or_inconsistent_data. Accessed 13 December 2011."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2012.33"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0139-2"},{"key":"e_1_2_1_8_1","first-page":"243","volume-title":"VLDB","author":"Agrawal D.","year":"1990"},{"key":"e_1_2_1_9_1","first-page":"151","volume-title":"VLDB","author":"Agrawal D.","year":"1992"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561927_6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11864219_31"},{"key":"e_1_2_1_12_1","first-page":"249","volume-title":"CIDR","author":"Alvaro P.","year":"2011"},{"key":"e_1_2_1_13_1","first-page":"181","volume-title":"VLDB","author":"Armbrust M.","year":"2012"},{"key":"e_1_2_1_14_1","unstructured":"Basho Technologies Inc. Riak wiki: Riak &gt; concepts &gt; replication. http:\/\/wiki.basho.com\/Replication.html. Accessed 13 December 2011.  Basho Technologies Inc. Riak wiki: Riak &gt; concepts &gt; replication. http:\/\/wiki.basho.com\/Replication.html. Accessed 13 December 2011."},{"key":"e_1_2_1_15_1","unstructured":"Basho Technologies Inc. riak_kv 1.0 application. https:\/\/github.com\/basho\/riak_kv\/blob\/1.0\/src\/riak_kv_app.erl.  Basho Technologies Inc. riak_kv 1.0 application. https:\/\/github.com\/basho\/riak_kv\/blob\/1.0\/src\/riak_kv_app.erl."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2093185.2093186"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1556154.1556172"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/5505.5508"},{"key":"e_1_2_1_19_1","unstructured":"J. Dean. Designs lessons and advice from building large distributed systems. Keynote from LADIS 2009.  J. Dean. Designs lessons and advice from building large distributed systems. Keynote from LADIS 2009."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41841"},{"key":"e_1_2_1_22_1","unstructured":"J. B. Ellis. Revision 986783: revert 'per-connection read-your-writes \"session\" consistency'. http:\/\/svn.apache.org\/viewvc?view=revision&revision=986783. 18 August 2010 one week after the original patch was accepted.  J. B. Ellis. Revision 986783: revert 'per-connection read-your-writes \"session\" consistency'. http:\/\/svn.apache.org\/viewvc?view=revision&revision=986783. 18 August 2010 one week after the original patch was accepted."},{"key":"e_1_2_1_23_1","volume-title":"30 November","author":"Feinberg A.","year":"2011"},{"key":"e_1_2_1_24_1","volume-title":"ICDE, 2011","author":"Feinberg A.","year":"2012"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.569655"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/800215.806583"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/564585.564601"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993834"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073829"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"C. Hale. Personal communication. 16 November 2011.  C. Hale. Personal communication. 16 November 2011.","DOI":"10.2979\/ethicsenviro.16.2.37"},{"key":"e_1_2_1_31_1","unstructured":"C. Hale and R. Kennedy. Using Riak at Yammer. http:\/\/dl.dropbox.com\/u\/2744222\/2011-03-22_Riak-At-Yammer.pdf. 23 March 2011.  C. Hale and R. Kennedy. Using Riak at Yammer. http:\/\/dl.dropbox.com\/u\/2744222\/2011-03-22_Riak-At-Yammer.pdf. 23 March 2011."},{"key":"e_1_2_1_32_1","unstructured":"J. Hamilton. Perspectives: I love eventual consistency but... http:\/\/perspectives.mvdirona.com\/2010\/02\/24\/ILoveEventualConsistencyBut.aspx. 24 February 2010.  J. Hamilton. Perspectives: I love eventual consistency but... http:\/\/perspectives.mvdirona.com\/2010\/02\/24\/ILoveEventualConsistencyBut.aspx. 24 February 2010."},{"key":"e_1_2_1_33_1","volume-title":"CIDR","author":"Helland P.","year":"2009"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/22952.22953"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_36_1","first-page":"145","volume-title":"USENIX ATC","author":"Hunt P.","year":"2010"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/937598.937601"},{"key":"e_1_2_1_38_1","unstructured":"D. King. keltranis comment on \"reddit's now running on Cassandra\". http:\/\/www.reddit.com\/r\/programming\/comments\/bcqhi\/reddits_now_running_on_cassandra\/c0m3wh6. March 2010.  D. King. keltranis comment on \"reddit's now running on Cassandra\". http:\/\/www.reddit.com\/r\/programming\/comments\/bcqhi\/reddits_now_running_on_cassandra\/c0m3wh6. March 2010."},{"key":"e_1_2_1_39_1","unstructured":"J. Kirkell. Consistency or bust: Breaking a Riak cluster. http:\/\/www.oscon.com\/oscon2011\/public\/schedule\/detail\/19762. Talk at O'Reilly OSCON 2011 27 July 2011.  J. Kirkell. Consistency or bust: Breaking a Riak cluster. http:\/\/www.oscon.com\/oscon2011\/public\/schedule\/detail\/19762. Talk at O'Reilly OSCON 2011 27 July 2011."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2003.1247672"},{"key":"e_1_2_1_41_1","first-page":"35","volume-title":"LADIS","author":"Lakshman A.","year":"2008"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/279227.279229"},{"key":"e_1_2_1_44_1","unstructured":"G. Linden. Make data useful. https:\/\/sites.google.com\/site\/glinden\/Home\/StanfordDataMining.2006-11-29.ppt. 29 November 2006.  G. Linden. Make data useful. https:\/\/sites.google.com\/site\/glinden\/Home\/StanfordDataMining.2006-11-29.ppt. 29 November 2006."},{"key":"e_1_2_1_45_1","unstructured":"G. Linden. Marissa Mayer at Web 2.0. http:\/\/glinden.blogspot.com\/2006\/11\/marissa-mayer-at-web-20.html. 9 November 2006.  G. Linden. Marissa Mayer at Web 2.0. http:\/\/glinden.blogspot.com\/2006\/11\/marissa-mayer-at-web-20.html. 9 November 2006."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043593"},{"key":"e_1_2_1_47_1","unstructured":"J. Lynch. Rolling with Riak. http:\/\/sdruby.org\/podcast\/81. Talk presented at SD Ruby meeting (Podcast 81) 2010.  J. Lynch. Rolling with Riak. http:\/\/sdruby.org\/podcast\/81. Talk presented at SD Ruby meeting (Podcast 81) 2010."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3054"},{"key":"e_1_2_1_50_1","first-page":"185","volume-title":"The Architecture of Open Source Applications","author":"Marcus A.","year":"2011"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/2172338.2172348"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795281232"},{"key":"e_1_2_1_53_1","volume-title":"Network Storage Symposium","author":"Noble B.","year":"1999"},{"key":"e_1_2_1_54_1","first-page":"144","volume-title":"VLDB","author":"Olston C.","year":"2000"},{"key":"e_1_2_1_55_1","unstructured":"Outbrain Inc. Introduction to no:sql {sic} and Cassandra (and Outbrain). https:\/\/docs.google.com\/present\/view?id=ahbp3bktzpkc_220f7v26vg7. January 2010.  Outbrain Inc. Introduction to no:sql {sic} and Cassandra (and Outbrain). https:\/\/docs.google.com\/present\/view?id=ahbp3bktzpkc_220f7v26vg7. January 2010."},{"key":"e_1_2_1_56_1","volume-title":"Velocity Web Performance and Operations Conference","author":"Schurman E.","year":"2009"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043592"},{"key":"e_1_2_1_58_1","volume-title":"VoltDB Webinar","author":"Stonebraker M.","year":"2010"},{"key":"e_1_2_1_59_1","unstructured":"R. Sumbaly. Writing own client for voldemort. https:\/\/github.com\/voldemort\/voldemort\/wiki\/Writing-own-client-for-Voldemort. 16 June 2011 (accessed 21 December 2011).  R. Sumbaly. Writing own client for voldemort. https:\/\/github.com\/voldemort\/voldemort\/wiki\/Writing-own-client-for-Voldemort. 16 June 2011 (accessed 21 December 2011)."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.5555\/645792.668302"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1435417.1435432"},{"key":"e_1_2_1_62_1","first-page":"134","volume-title":"CIDR","author":"Wada H.","year":"2011"},{"key":"e_1_2_1_63_1","first-page":"245","volume-title":"NSDI","author":"Wester B."},{"key":"e_1_2_1_64_1","unstructured":"D. Williams. HBase vs Cassandra: why we moved. http:\/\/ria101.wordpress.com\/2010\/02\/24\/hbase-vs-cassandra-why-we-moved. 24 February 2010.  D. Williams. HBase vs Cassandra: why we moved. http:\/\/ria101.wordpress.com\/2010\/02\/24\/hbase-vs-cassandra-why-we-moved. 24 February 2010."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/566340.566342"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1124153.1124156"},{"key":"e_1_2_1_67_1","first-page":"687","volume-title":"ICDCS","author":"Zhang C.","year":"2003"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2212351.2212359","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:36:05Z","timestamp":1672220165000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2212351.2212359"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4]]},"references-count":66,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["10.14778\/2212351.2212359"],"URL":"https:\/\/doi.org\/10.14778\/2212351.2212359","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,4]]}}}