Arbitration-Free Consistency Is Available (and Vice Versa)
Open Access
- 8 January 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (POPL) , 1183-1211
Abstract
The fundamental tension between availability 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. 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). Within this framework, we prove the Arbitration-Free Consistency (AFC) theorem, showing that an object specification within a consistency model admits an available implementation if and only if it is arbitration-free, that is, it does not require a total arbitration order to resolve visibility or read dependencies. The AFC theorem unifies and generalizes previous results, revealing arbitration-freedom as the fundamental property that delineates coordination-free consistency from inherently synchronized behavior.Keywords
All Related Versions
Funding Information
- Israel Science Foundation (22/1425)
- Israel Science Foundation (25/1849)
- Agence Nationale de la Recherche (CENTEANES)
This publication has 23 references indexed in Scilit:
- On the Complexity of Checking Mixed Isolation Levels for SQL Transactions2025
- Limitations of Highly-Available Eventually-Consistent Data StoresIEEE Transactions on Parallel and Distributed Systems, 2016
- The potential dangers of causal consistency and an explicit solution2012
- Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the StoryComputer, 2012
- Don't settle for eventual2011
- Transactional storage for geo-replicated systems2011
- Conflict-Free Replicated Data Types2011
- The declarative imperativeACM SIGMOD Record, 2010
- Generalized isolation level definitions2002
- Sequential consistency versus linearizabilityACM Transactions on Computer Systems, 1994