[POPL'26] Arbitration-Free Consistency Is Available (and Vice Versa) скачать в хорошем качестве

[POPL'26] Arbitration-Free Consistency Is Available (and Vice Versa)

Arbitration-Free Consistency Is Available (and Vice Versa) (Video, POPL 2026) Hagit Attiya, Constantin Enea, Enrique Román-Calvo (Technion - Israel Institute of Technology, Israel; LIX - Ecole Polytechnique - CNRS - Institut Polytechnique de Paris, France; University of Freiburg, Germany) 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. Article: https://doi.org/10.1145/3776683 ORCID: https://orcid.org/0000-0002-8017-6457, https://orcid.org/0000-0003-2727-8865, https://orcid.org/0009-0005-7539-2330 Video Tags: Distributed Systems, Availability, CAP Theorem, doi:10.1145/3776683, orcid:0000-0002-8017-6457, orcid:0000-0003-2727-8865, orcid:0009-0005-7539-2330 Presentation at the POPL 2026 conference, Jan 11-17, 2026, https://popl26.sigplan.org/ Sponsored by ACM SIGPLAN.