{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T14:12:24Z","timestamp":1784211144337,"version":"3.55.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T00:00:00Z","timestamp":1767830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["22\/1425"],"award-info":[{"award-number":["22\/1425"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["25\/1849"],"award-info":[{"award-number":["25\/1849"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","award":["CENTEANES"],"award-info":[{"award-number":["CENTEANES"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,1,8]]},"abstract":"<jats:p>\n                    The fundamental tension between\n                    <jats:italic toggle=\"yes\">availability<\/jats:italic>\n                    and consistency shapes the design of distributed storage systems. Classical results capture extreme points of this trade-off: the CAP theorem shows that strong models like linearizability preclude availability under partitions, while weak models like causal consistency remain implementable without coordination. These theorems apply to simple read-write interfaces, leaving open a precise explanation of the combinations of object semantics and consistency models that admit available implementations.\n                  <\/jats:p>\n                  <jats:p>This paper develops a general semantic framework in which storage specifications combine operation semantics and consistency models. The framework encompasses a broad range of objects (key-value stores, counters, sets, CRDTs, and SQL databases) and consistency models (from causal consistency and sequential consistency to snapshot isolation and bounded staleness).<\/jats:p>\n                  <jats:p>\n                    Within this framework, we prove the\n                    <jats:italic toggle=\"yes\">Arbitration-Free Consistency<\/jats:italic>\n                    (AFC) theorem, showing that an object specification within a consistency model admits an available implementation if and only if it is\n                    <jats:italic toggle=\"yes\">arbitration-free<\/jats:italic>\n                    , that is, it does not require a total arbitration order to resolve visibility or read dependencies.\n                  <\/jats:p>\n                  <jats:p>The AFC theorem unifies and generalizes previous results, revealing arbitration-freedom as the fundamental property that delineates coordination-free consistency from inherently synchronized behavior.<\/jats:p>","DOI":"10.1145\/3776683","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T18:59:43Z","timestamp":1767898783000},"page":"1183-1211","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Arbitration-Free Consistency Is Available (and Vice Versa)"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8017-6457","authenticated-orcid":false,"given":"Hagit","family":"Attiya","sequence":"first","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2727-8865","authenticated-orcid":false,"given":"Constantin","family":"Enea","sequence":"additional","affiliation":[{"name":"LIX - Ecole Polytechnique - CNRS - Institut Polytechnique de Paris, Palaiseau, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-7539-2330","authenticated-orcid":false,"given":"Enrique","family":"Rom\u00e1n-Calvo","sequence":"additional","affiliation":[{"name":"University of Freiburg, Freiburg im Breisgau, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2012.33"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2000.839388"},{"key":"e_1_3_2_4_2","unstructured":"Peter Alvaro Neil Conway Joseph M. Hellerstein and William R. Marczak. 2011. Consistency Analysis in Bloom: a CALM and Collected Approach. In Fifth Biennial Conference on Innovative Data Systems Research CIDR 2011 Asilomar CA USA January 9-12 2011 Online Proceedings. www.cidrdb.org 249\u2013260. http:\/\/cidrdb.org\/cidr2011\/Papers\/CIDR11_Paper35.pdf"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2809784"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450151"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2556669"},{"key":"e_1_3_2_8_2","unstructured":"Hagit Attiya Constantin Enea and Enrique Rom\u00e1n-Calvo. 2025. Arbitration-Free Consistency is Available (and Vice Versa). arXiv:2510.21304 [cs.DC] https:\/\/arxiv.org\/abs\/2510.21304"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/176575.176576"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","unstructured":"Peter Bailis Alan Fekete Ali Ghodsi Joseph M. Hellerstein and Ion Stoica. 2012. The Potential Dangers of Causal Consistency and an Explicit Solution. In Proceedings of the 3rd ACM Symposium on Cloud Computing. http:\/\/doi.acm.org\/10.1145\/2391229.2391251 10.1145\/2391229.2391251","DOI":"10.1145\/2391229.2391251"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","unstructured":"Peter Bailis Ali Ghodsi Joseph M. Hellerstein and Ion Stoica. 2013. Bolt-on Causal Consistency. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. 761\u2013772. http:\/\/doi.acm.org\/10.1145\/2463676.2465279 10.1145\/2463676.2465279","DOI":"10.1145\/2463676.2465279"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3360591"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-98685-7_15"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/343477.343502"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1561\/2500000011"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","unstructured":"Sebastian Burckhardt Alexey Gotsman Hongseok Yang and Marek Zawirski. 2014. Replicated data types: specification verification optimality. In 41st Symposium on Principles of Programming Languages POPL. ACM 271\u2013284. https:\/\/doi.org\/10.1145\/2535838.2535848 10.1145\/2535838.2535848","DOI":"10.1145\/2535838.2535848"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ECOOP.2015.568"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","unstructured":"Andrea Cerone Giovanni Bernardi and Alexey Gotsman. 2015. A Framework for Transactional Consistency Models with Atomic Visibility. In 26th International Conference on Concurrency Theory CONCUR. 58\u201371. https:\/\/doi.org\/10.4230\/LIPICS.CONCUR.2015.58 10.4230\/LIPICS.CONCUR.2015.58","DOI":"10.4230\/LIPICS.CONCUR.2015.58"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/564585.564601"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3197406.3197420"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1860702.1860704"},{"key":"e_1_3_2_22_2","unstructured":"Martin Kleppmann. 2015. A Critique of the CAP Theorem. CoRR abs\/1509.05393 (2015). arXiv:1509.05393 http:\/\/arxiv.org\/abs\/1509.05393"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574268"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_3_2_25_2","volume-title":"PRAM: A scalable shared memory. Technical Report TR-180-88","author":"Lipton Richard J","year":"1988","unstructured":"Richard J Lipton and Jonathan S Sandberg. 1988. PRAM: A scalable shared memory. Technical Report TR-180-88. Princeton University, Department of Computer Science."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","unstructured":"Wyatt Lloyd Michael J. Freedman Michael Kaminsky and David G. Andersen. 2011. Don\u2019t Settle for Eventual: Scalable Causal Consistency for Wide-area Storage with COPS. In Proceedings of the 23rd ACM Symposium on Operating Systems Principles. 401\u2013416. http:\/\/doi.acm.org\/10.1145\/2043556.2043593 10.1145\/2043556.2043593","DOI":"10.1145\/2043556.2043593"},{"key":"e_1_3_2_27_2","first-page":"313","volume-title":"In Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2013, Lombard, IL, USA, April 2-5, 2013","author":"Lloyd Wyatt","year":"2013","unstructured":"Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. 2013. Stronger Semantics for Low-Latency Geo-Replicated Storage. In Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2013, Lombard, IL, USA, April 2-5, 2013, Nick Feamster and Jeffrey C. Mogul (Eds.). USENIX Association, 313\u2013328. https:\/\/www.usenix.org\/conference\/nsdi13\/technical-sessions\/presentation\/lloyd"},{"key":"e_1_3_2_28_2","first-page":"158","volume-title":"Consistency, availability, and convergence","author":"Mahajan Prince","year":"2011","unstructured":"Prince Mahajan, Lorenzo Alvisi, Mike Dahlin, et al. 2011. Consistency, availability, and convergence. University of Texas at Austin Tech Report 11 (2011), 158."},{"key":"e_1_3_2_29_2","unstructured":"Microsoft. 2022. Consistency Levels in Azure Cosmos DB. https:\/\/docs.microsoft.com\/en-us\/azure\/cosmos-db\/consistency-levels."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24550-3_29"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043592"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3776683","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T13:40:47Z","timestamp":1784209247000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3776683"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":30,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2026,1,8]]}},"alternative-id":["10.1145\/3776683"],"URL":"https:\/\/doi.org\/10.1145\/3776683","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"assertion":[{"value":"2025-07-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}