{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T04:06:03Z","timestamp":1780632363654,"version":"3.54.1"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,11]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.14778\/2735508.2735509","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"185-196","source":"Crossref","is-referenced-by-count":143,"title":["Coordination avoidance in database systems"],"prefix":"10.14778","volume":"8","author":[{"given":"Peter","family":"Bailis","sequence":"first","affiliation":[{"name":"UC Berkeley"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan","family":"Fekete","sequence":"additional","affiliation":[{"name":"University of Sydney"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael J.","family":"Franklin","sequence":"additional","affiliation":[{"name":"UC Berkeley"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ali","family":"Ghodsi","sequence":"additional","affiliation":[{"name":"UC Berkeley"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph M.","family":"Hellerstein","sequence":"additional","affiliation":[{"name":"UC Berkeley"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ion","family":"Stoica","sequence":"additional","affiliation":[{"name":"UC Berkeley"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2012.33"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/155271.155276"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130296"},{"key":"e_1_2_1_5_1","volume-title":"CIDR","author":"Alvaro P.","year":"2011","unstructured":"P. Alvaro , N. Conway , J. M. Hellerstein , and W. Marczak . Consistency analysis in Bloom: a CALM and collected approach . In CIDR 2011 . P. Alvaro, N. Conway, J. M. Hellerstein, and W. Marczak. Consistency analysis in Bloom: a CALM and collected approach. In CIDR 2011."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2523616.2523632"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450151"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926442"},{"key":"e_1_2_1_9_1","volume-title":"VLDB","author":"Bailis P.","year":"2014","unstructured":"P. Bailis , A. Davidson , A. Fekete , A. Ghodsi , J. M. Hellerstein , and I. Stoica . Highly Available Transactions: Virtues and limitations . In VLDB 2014 . P. Bailis, A. Davidson, A. Fekete, A. Ghodsi, J. M. Hellerstein, and I. Stoica. Highly Available Transactions: Virtues and limitations. In VLDB 2014."},{"key":"e_1_2_1_10_1","volume-title":"Coordination avoidance in database systems (Extended version)","author":"Bailis P.","year":"2014","unstructured":"P. Bailis , A. Fekete , M. J. Franklin , A. Ghodsi , Coordination avoidance in database systems (Extended version) . 2014 . arXiv: 1402.2237. P. Bailis, A. Fekete, M. J. Franklin, A. Ghodsi, et al. Coordination avoidance in database systems (Extended version). 2014. arXiv: 1402.2237."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588562"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2460276.2462076"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2639988.2639988"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00122147"},{"key":"e_1_2_1_15_1","volume-title":"Addison-wesley New York","author":"Bernstein P.","year":"1987","unstructured":"P. Bernstein , V. Hadzilacos , and N. Goodman . Concurrency control and recovery in database systems . Addison-wesley New York , 1987 . P. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency control and recovery in database systems. Addison-wesley New York, 1987."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/320128.320131"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28869-2_4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522712"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391230"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454167"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/5505.5508"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_2_1_23_1","volume-title":"VLDB","author":"Difallah D. E.","year":"2014","unstructured":"D. E. Difallah , A. Pavlo , C. Curino , and P. Cudre-Mauroux . OLTP-Bench: An extensible testbed for benchmarking relational databases . In VLDB 2014 . D. E. Difallah, A. Pavlo, C. Curino, and P. Cudre-Mauroux. OLTP-Bench: An extensible testbed for benchmarking relational databases. In VLDB 2014."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778180.1778201"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/360363.360369"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/319983.319985"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38742"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/564585.564601"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/978-1-4615-5643-5_9","volume-title":"Logics for databases and information systems","author":"Godfrey P.","year":"1998","unstructured":"P. Godfrey Logics for databases and information systems , chapter Integrity constraints: Semantics and applications, pages 265 -- 306 . Springer , 1998 . P. Godfrey et al. Logics for databases and information systems, chapter Integrity constraints: Semantics and applications, pages 265--306. Springer, 1998."},{"key":"e_1_2_1_30_1","volume-title":"VLDB","author":"Gray J.","year":"1981","unstructured":"J. Gray . The transaction concept: Virtues and limitations . In VLDB 1981 . J. Gray. The transaction concept: Virtues and limitations. In VLDB 1981."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132867"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0169-023X(93)90008-D"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170048"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0312-3"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807233"},{"key":"e_1_2_1_36_1","volume-title":"Stichting Mathematisch Centrum Amsterdam","author":"Klop J. W.","year":"1990","unstructured":"J. W. Klop . Term rewriting systems . Stichting Mathematisch Centrum Amsterdam , 1990 . J. W. Klop. Term rewriting systems. Stichting Mathematisch Centrum Amsterdam, 1990."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/50202.50248"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582114"},{"key":"e_1_2_1_39_1","volume-title":"CCA","author":"Lamport L.","year":"1976","unstructured":"L. Lamport . Towards a theory of correctness for multi-user database systems. Technical report , CCA , 1976 . Described in {3, 49}. L. Lamport. Towards a theory of correctness for multi-user database systems. Technical report, CCA, 1976. Described in {3, 49}."},{"key":"e_1_2_1_40_1","volume-title":"USENIX ATC","author":"Li C.","year":"2014","unstructured":"C. Li , J. Leitao , A. Clement , N. Pregui\u00e7a , R. Rodrigues , Automating the choice of consistency levels in replicated systems . In USENIX ATC 2014 . C. Li, J. Leitao, A. Clement, N. Pregui\u00e7a, R. Rodrigues, et al. Automating the choice of consistency levels in replicated systems. In USENIX ATC 2014."},{"key":"e_1_2_1_41_1","volume-title":"OSDI","author":"Li C.","year":"2012","unstructured":"C. Li , D. Porto , A. Clement , J. Gehrke , Making geo-replicated systems fast as possible, consistent when necessary . In OSDI 2012 . C. Li, D. Porto, A. Clement, J. Gehrke, et al. Making geo-replicated systems fast as possible, consistent when necessary. In OSDI 2012."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538909.1538913"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.34"},{"key":"e_1_2_1_44_1","volume-title":"Atomic Transactions: In Concurrent and Distributed Systems","author":"Lynch N. A.","year":"1993","unstructured":"N. A. Lynch , M. Merritt , W. Weihl , and A. Fekete . Atomic Transactions: In Concurrent and Distributed Systems . Morgan Kaufmann Publishers Inc ., 1993 . N. A. Lynch, M. Merritt, W. Weihl, and A. Fekete. Atomic Transactions: In Concurrent and Distributed Systems. Morgan Kaufmann Publishers Inc., 1993."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/268998.266711"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448947"},{"key":"e_1_2_1_47_1","volume-title":"Writes that fall in the forest and make no sound: Semantics-based adaptive data consistency","author":"Roy S.","year":"2014","unstructured":"S. Roy , L. Kot , Writes that fall in the forest and make no sound: Semantics-based adaptive data consistency , 2014 . arXiv: 1403.2307. S. Roy, L. Kot, et al. Writes that fall in the forest and make no sound: Semantics-based adaptive data consistency, 2014. arXiv: 1403.2307."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1057977.1057980"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/263944"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/211414.211427"},{"key":"e_1_2_1_52_1","volume-title":"VLDB","author":"Stonebraker M.","year":"2007","unstructured":"M. Stonebraker , S. Madden , D. J. Abadi , S. Harizopoulos , The end of an architectural era: (it's time for a complete rewrite) . In VLDB 2007 . M. Stonebraker, S. Madden, D. J. Abadi, S. Harizopoulos, et al. The end of an architectural era: (it's time for a complete rewrite). In VLDB 2007."},{"key":"e_1_2_1_53_1","volume-title":"Principles of distributed database systems","author":"Tamer \u00d6zsu M.","year":"2011","unstructured":"M. Tamer \u00d6zsu and P. Valduriez . Principles of distributed database systems . Springer , 2011 . M. Tamer \u00d6zsu and P. Valduriez. Principles of distributed database systems. Springer, 2011."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213838"},{"key":"e_1_2_1_55_1","volume-title":"TPC Benchmark C revision 5.11","author":"TPC Council","year":"2010","unstructured":"TPC Council . TPC Benchmark C revision 5.11 , 2010 . TPC Council. TPC Benchmark C revision 5.11, 2010."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/319732.319734"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522713"},{"key":"e_1_2_1_59_1","volume-title":"Morgan Kaufmann","author":"Widom J.","year":"1996","unstructured":"J. Widom and S. Ceri . Active database systems: Triggers and rules for advanced database processing . Morgan Kaufmann , 1996 . J. Widom and S. Ceri. Active database systems: Triggers and rules for advanced database processing. Morgan Kaufmann, 1996."},{"key":"e_1_2_1_60_1","volume-title":"NSDI","author":"Xu Y.","year":"2013","unstructured":"Y. Xu : avoiding long tails in the cloud . In NSDI 2013 . Y. Xu et al. Bobtail: avoiding long tails in the cloud. In NSDI 2013."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2735508.2735509","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:28:05Z","timestamp":1672223285000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2735508.2735509"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,11]]}},"alternative-id":["10.14778\/2735508.2735509"],"URL":"https:\/\/doi.org\/10.14778\/2735508.2735509","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,11]]}}}