{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:49:07Z","timestamp":1750308547216,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"8","license":[{"start":{"date-parts":[[2014,8,1]],"date-time":"2014-08-01T00:00:00Z","timestamp":1406851200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2014,8]]},"abstract":"

Data replication results in a fundamental trade-off between operation latency and consistency. At the weak end of the spectrum of possible consistency models is eventual consistency, which provides no limit to the staleness of data returned. However, anecdotally, eventual consistency is often \"good enough\" for practitioners given its latency and availability benefits. In this work, we explain this phenomenon and demonstrate that, despite their weak guarantees, eventually consistent systems regularly return consistent data while providing lower latency than their strongly consistent counterparts. To quantify the behavior of eventually consistent stores, we introduce Probabilistically Bounded Staleness (PBS), a consistency model that provides expected bounds on data staleness with respect to both versions and wall clock time. We derive a closed-form solution for version-based staleness and model real-time staleness for a large class of quorum replicated, Dynamo-style stores. Using PBS, we measure the trade-off between latency and consistency for partial, non-overlapping quorum systems under Internet production workloads. We quantitatively demonstrate how and why eventually consistent systems frequently return consistent data within tens of milliseconds while offering large latency benefits.","DOI":"10.1145\/2632792","type":"journal-article","created":{"date-parts":[[2014,7,24]],"date-time":"2014-07-24T15:46:18Z","timestamp":1406216778000},"page":"93-102","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Quantifying eventual consistency with PBS"],"prefix":"10.1145","volume":"57","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":[[2014,8]]},"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\/11561927_6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11864219_31"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2460276.2462076"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212359"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465260"},{"key":"e_1_2_1_7_1","unstructured":"Bailis P. Venkataraman S. Franklin M.J. Hellerstein J.M. Stoica I. Quantifying eventual consistency with PBS. VLDB J. (2014). (see http:\/\/link.springer.com\/article\/10.1007\/s00778-013-0330-1). Bailis P. Venkataraman S. Franklin M.J. Hellerstein J.M. Stoica I. Quantifying eventual consistency with PBS. VLDB J . (2014). (see http:\/\/link.springer.com\/article\/10.1007\/s00778-013-0330-1)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454167"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/5505.5508"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993834"},{"key":"e_1_2_1_12_1","unstructured":"Hamilton J. Perspectives: I love eventual consistency but\u2026 http:\/\/perspectives.mvdirona.com\/2010\/02\/24\/ILoveEventualConsistencyBut.aspx (24 Feb. 2010). Hamilton J. Perspectives: I love eventual consistency but\u2026 http:\/\/perspectives.mvdirona.com\/2010\/02\/24\/ILoveEventualConsistencyBut.aspx (24 Feb. 2010)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_14_1","unstructured":"Kirkell J. Consistency or bust: Breaking a Riak cluster. http:\/\/www.oscon.com\/oscon2011\/public\/schedule\/detail\/19762. Talk at O'Reilly OSCON 2011 (27 Jul. 2011). Kirkell J. Consistency or bust: Breaking a Riak cluster. http:\/\/www.oscon.com\/oscon2011\/public\/schedule\/detail\/19762. Talk at O'Reilly OSCON 2011 (27 Jul. 2011)."},{"key":"e_1_2_1_15_1","unstructured":"Linden G. Make data useful. https:\/\/sites.google.com\/site\/glinden\/Home\/StanfordDataMining.2006-11-29.ppt (29 Nov. 2006). Linden G. Make data useful. https:\/\/sites.google.com\/site\/glinden\/Home\/StanfordDataMining.2006-11-29.ppt (29 Nov. 2006)."},{"key":"e_1_2_1_16_1","unstructured":"Linden G. Marissa Mayer at Web 2.0. http:\/\/glinden.blogspot.com\/2006\/11\/marissa-mayer-at-web-20.html (9 Nov. 2006). Linden G. Marissa Mayer at Web 2.0. http:\/\/glinden.blogspot.com\/2006\/11\/marissa-mayer-at-web-20.html (9 Nov. 2006)."},{"volume-title":"NSDI","year":"2013","author":"Lloyd W.","key":"e_1_2_1_17_1"},{"volume-title":"Technical Report TR-11-22, Computer Science Department","year":"2011","author":"Mahajan P.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3054"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Merideth M. Reiter M.\n \n \n \n Selected results from the latest decade of quorum systems research\n . In Replication B. Charron-Bost F. Pedone and A. Schiper eds. Volume \n 5959\n of \n LNCS (2010)\n . \n Springer 185--206. Merideth M. Reiter M. Selected results from the latest decade of quorum systems research. In Replication B. Charron-Bost F. Pedone and A. Schiper eds. Volume 5959 of LNCS (2010). Springer 185--206.","DOI":"10.1007\/978-3-642-11294-2_10"},{"volume-title":"Proceedings of the 8th Workshop on Hot Topics in System Dependability","year":"2012","author":"Rahman M.","key":"e_1_2_1_21_1"},{"volume-title":"Velocity Web Performance and Operations Conference","year":"2009","author":"Schurman E.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043592"},{"key":"e_1_2_1_24_1","unstructured":"Stonebraker M. Urban myths about SQL. http:\/\/voltdb.com\/_pdf\/VoltDB-MikeStonebrakerSQLMythsWebinar-060310.pdf. VoltDB Webinar (Jun. 2010). Stonebraker M. Urban myths about SQL. http:\/\/voltdb.com\/_pdf\/VoltDB-MikeStonebrakerSQLMythsWebinar-060310.pdf. VoltDB Webinar (Jun. 2010)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/381992.383631"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1435417.1435432"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/566340.566342"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2632792","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2632792","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:03:38Z","timestamp":1750273418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2632792"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":27,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.1145\/2632792"],"URL":"https:\/\/doi.org\/10.1145\/2632792","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2014,8]]},"assertion":[{"value":"2014-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}