2014/02/10 by Peter Bailis, Bailis, Peter, Alan Fekete +9
Computer Science · #Advanced Database Systems and Queries #Cloud Computing and Resource Management #Databases (cs.DB) #Distributed systems and fault tolerance #FOS: Computer and information sciences #cs.DB
paper · pdf · doi:10.48550/arxiv.1402.2237
Extended version of paper appearing in PVLDB Vol. 8, No. 3
openalex publication_date 2014/02/10 · arxiv created 2014/10/30 · arxiv updated 2014/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Minimizing coordination, or blocking communication between concurrently executing operations, is key to maximizing scalability, availability, and high performance in database systems. However, uninhibited coordination-free execution can compromise application correctness, or consistency. When is coordination necessary for correctness? The classic use of serializable transactions is sufficient to maintain correctness but is not necessary for all applications, sacrificing potential scalability. In this paper, we develop a formal framework, invariant confluence, that determines whether an application requires coordination for correct execution. By operating on application-level invariants over database states (e.g., integrity constraints), invariant confluence analysis provides a necessary and sufficient condition for safe, coordination-free execution. When programmers specify their application invariants, this analysis allows databases to coordinate only when anomalies that might violate invariants are possible. We analyze the invariant confluence of common invariants and operations from real-world database systems (i.e., integrity constraints) and applications and show that many are invariant confluent and therefore achievable without coordination. We apply these results to a proof-of-concept coordination-avoiding database prototype and demonstrate sizable performance gains compared to serializable execution, notably a 25-fold improvement over prior TPC-C New-Order performance on a 200 server cluster.