{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T12:43:31Z","timestamp":1770295411001,"version":"3.49.0"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>Causal consistency is an attractive consistency model for geo-replicated data stores. It is provably the strongest model that tolerates network partitions. It avoids the long latencies associated with strong consistency, and, especially when using read-only transactions (ROTs), it prevents many of the anomalies of weaker consistency models. Recent work has shown that causal consistency allows \"latency-optimal\" ROTs, that are nonblocking, single-round and single-version in terms of communication. On the surface, this latency optimality is very appealing, as the vast majority of applications are assumed to have read-dominated workloads.<\/jats:p>\n          <jats:p>In this paper, we show that such \"latency-optimal\" ROTs induce an extra overhead on writes that is so high that it actually jeopardizes performance even in read-dominated workloads. We show this result from a practical as well as from a theoretical angle.<\/jats:p>\n          <jats:p>We present the Contrarian protocol that implements \"almost latency-optimal\" ROTs, but that does not impose on the writes any of the overheads incurred by latency-optimal protocols. In Contrarian, ROTs are nonblocking and single-version, but they require two rounds of client-server communication. We experimentally show that this protocol not only achieves higher throughput, but, surprisingly, also provides better latencies for all but the lowest loads and the most read-heavy workloads.<\/jats:p>\n          <jats:p>\n            We furthermore prove that the extra overhead imposed on writes by latency-optimal ROTs is inherent, i.e., it is not an artifact of the design we consider, and cannot be avoided by\n            <jats:italic>any<\/jats:italic>\n            implementation of latency-optimal ROTs. We show in particular that this overhead grows linearly with the number of clients.\n          <\/jats:p>","DOI":"10.14778\/3236187.3236210","type":"journal-article","created":{"date-parts":[[2018,9,10]],"date-time":"2018-09-10T12:12:28Z","timestamp":1536581548000},"page":"1618-1632","source":"Crossref","is-referenced-by-count":23,"title":["Causal consistency and latency optimality"],"prefix":"10.14778","volume":"11","author":[{"given":"Diego","family":"Didona","sequence":"first","affiliation":[{"name":"EPFL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rachid","family":"Guerraoui","sequence":"additional","affiliation":[{"name":"EPFL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingjing","family":"Wang","sequence":"additional","affiliation":[{"name":"EPFL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Willy","family":"Zwaenepoel","sequence":"additional","affiliation":[{"name":"EPFL and University of Sydney"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,7]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01784241"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2016.98"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465361"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2685048.2685077"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254766"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767419"},{"key":"e_1_2_1_8_1","first-page":"55","volume-title":"Distributed Systems (2Nd Ed.)","author":"Babao\u011flu O.","year":"1993"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056103"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391251"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465279"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741972"},{"issue":"1","key":"e_1_2_1_13_1","first-page":"81","article-title":"Geo-replication: Fast if possible, consistent if necessary","volume":"39","author":"Balegas V.","year":"2016","journal-title":"Data Engineering Bulletin"},{"key":"e_1_2_1_14_1","volume-title":"2017 USENIX Annual Technical Conference (USENIX ATC 17)","author":"Balmau O.","year":"2017"},{"key":"e_1_2_1_15_1","first-page":"5","volume-title":"Proceedings of the 3rd Conference on Networked Systems Design & Implementation -","volume":"3","author":"Belaramani N.","year":"2006"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133931"},{"key":"e_1_2_1_17_1","volume-title":"Concurrency Control and Recovery in Database Systems","author":"Bernstein P. A.","year":"1986"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/7351.7478"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064210"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043571"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087802"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882951"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2523616.2523628"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2670983"},{"key":"e_1_2_1_29_1","volume-title":"Protocol buffers. https:\/\/developers.google.com\/protocol-buffers\/","year":"2017"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837625"},{"key":"e_1_2_1_31_1","first-page":"83","volume-title":"2017 USENIX Annual Technical Conference (USENIX ATC 17)","author":"Gunawardhana C.","year":"2017"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.1990.89297"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454211"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465363"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/978-3-319-14472-6_2","volume-title":"Principles of Distributed Systems (OPODIS)","author":"Kulkarni S. S.","year":"2014"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/138873.138877"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132756"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2643634.2643664"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043593"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/2482626.2482657"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/3026877.3026889"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815426"},{"key":"e_1_2_1_46_1","first-page":"215","volume-title":"Parallel and Distributed Algorithms","author":"Mattern F.","year":"1989"},{"key":"e_1_2_1_47_1","first-page":"453","volume-title":"14th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2017","author":"Mehdi S. A.","year":"2017"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052603"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/160551.160553"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723729"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/2482626.2482663"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2903738"},{"key":"e_1_2_1_53_1","volume-title":"http:\/\/www.ntp.org","author":"NTP.","year":"2017"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322158"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/268998.266711"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2997654"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064209"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/SRDS.2017.27"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/582318.582339"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043592"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2017.192"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2018.00014"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522731"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/224056.224070"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/320071.320076"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056101"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2926965"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/1435417.1435432"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814576.2814733"},{"key":"e_1_2_1_70_1","first-page":"723","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)","author":"Zhang I.","year":"2016"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815404"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522729"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3236187.3236210","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:45:03Z","timestamp":1672220703000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3236187.3236210"}},"subtitle":["friend or foe?"],"short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":69,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["10.14778\/3236187.3236210"],"URL":"https:\/\/doi.org\/10.14778\/3236187.3236210","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,7]]}}}