Arbitration-Free Consistency Is Available (and Vice Versa)
summary
Claims a tight iff theorem: a storage specification admits an available implementation under partitions exactly when it is arbitration-free — no requirement for a global total order to resolve visibility. The paper builds a semantic framework covering key-value stores, CRDTs and SQL with consistency models from causal consistency to snapshot isolation, proves the easy direction by reducing to causal consistency and the hard direction by constructing an n+1‑event visibility cycle across two disconnected replicas to force a contradiction, and supplies a syntactic check (complexity unresolved).
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:04Distributed replicated storage systems
- 2:50Strong versus weak consistency
- 5:59CAP theorem overview
- 8:07Partial results characterization
- 9:16Consistency models with visibility formulas
- 12:27Arbitration free condition
- 13:09Proof outline of theorem
- 16:40Conclusion and future research
- 18:23Q&A
related talks
14mBolt-On Strong Consistency: Specification, Implementation, and Verification
15mRethinking Safe Consistency in Distributed Object-Oriented Programming
22mHow to Enforce and Verify Invariants in Weakly Consistent Databases
41mConsistency without consensus in production systems
25mThe shell game called eventual consistency
13mThe ACID BASE Conundrum
18mDistributed Causal Memory for Higher-Order Distributed Separation Logic
43mWhat We Talk About When We Talk About Distributed Systems