{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T08:41:34Z","timestamp":1780994494261,"version":"3.54.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2019,10,10]],"date-time":"2019-10-10T00:00:00Z","timestamp":1570665600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2019,10,10]]},"abstract":"<jats:p>Transactions simplify concurrent programming by enabling computations on shared data that are isolated from other concurrent computations and are resilient to failures. Modern databases provide different consistency models for transactions corresponding to different tradeoffs between consistency and availability. In this work, we investigate the problem of checking whether a given execution of a transactional database adheres to some consistency model. We show that consistency models like read committed, read atomic, and causal consistency are polynomial-time checkable while prefix consistency and snapshot isolation are NP-complete in general. These results complement a previous NP-completeness result concerning serializability. Moreover, in the context of NP-complete consistency models, we devise algorithms that are polynomial time assuming that certain parameters in the input executions, e.g., the number of sessions, are fixed. We evaluate the scalability of these algorithms in the context of several production databases.<\/jats:p>","DOI":"10.1145\/3360591","type":"journal-article","created":{"date-parts":[[2019,10,11]],"date-time":"2019-10-11T14:53:33Z","timestamp":1570805613000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":45,"title":["On the complexity of checking transactional consistency"],"prefix":"10.1145","volume":"3","author":[{"given":"Ranadeep","family":"Biswas","sequence":"first","affiliation":[{"name":"University of Paris, France \/ IRIF, France \/ CNRS, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Constantin","family":"Enea","sequence":"additional","affiliation":[{"name":"University of Paris, France \/ IRIF, France \/ CNRS, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,10,10]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Bengt Jonsson, Magnus L\u00e5ng, Tuan Phong Ngo, and Konstantinos (Kostis) Sagonas.","author":"Abdulla Parosh Aziz","year":"2019"},{"key":"e_1_2_2_2_1","volume-title":"https:\/\/www.antidotedb.eu Retrieved March 28th","year":"2019"},{"key":"e_1_2_2_3_1","volume-title":"https:\/\/antidotedb.gitbook.io\/documentation\/overview\/configuration Retrieved March 28th","year":"2019"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223785"},{"key":"e_1_2_2_5_1","volume-title":"On the Complexity of Checking Transactional Consistency. abs\/1908.04509","author":"Biswas Ranadeep","year":"2019"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009888"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535848"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2015.568"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2015.58"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158119"},{"key":"e_1_2_2_11_1","volume-title":"https:\/\/github.com\/cockroachdb\/cockroach Retrieved March 28th","year":"2019"},{"key":"e_1_2_2_12_1","volume-title":"https:\/\/www.cockroachlabs.com\/docs\/v2.1\/transactions.html#isolation- levels Retrieved March 28th","year":"2019"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24605-3_37"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158113"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040315"},{"key":"e_1_2_2_16_1","volume-title":"http:\/\/galeracluster.com Retrieved March 28th","year":"2019"},{"key":"e_1_2_2_17_1","volume-title":"http:\/\/galeracluster.com\/documentation- webpages\/faq.html Retrieved March 28th","year":"2019"},{"key":"e_1_2_2_18_1","volume-title":"http:\/\/galeracluster.com\/documentation- webpages\/isolationlevels.html#intra- node- vs- inter- node- isolationin- galera- cluster Retrieved March 28th","year":"2019"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279614"},{"key":"e_1_2_2_20_1","volume-title":"http:\/\/jepsen.io Retrieved March 28th","author":"Kingsbury Kyle","year":"2019"},{"key":"e_1_2_2_21_1","volume-title":"https:\/\/github.com\/jepsen- io\/jepsen\/blob\/master\/galera\/src\/jepsen\/galera\/dirty_reads.clj Retrieved March 28th","author":"Kingsbury Kyle","year":"2019"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-17906-2_30"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276530"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322158"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/PDIS.1994.331722"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/512644.512661"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3360591","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3360591","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:22:59Z","timestamp":1750202579000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3360591"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,10]]},"references-count":27,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2019,10,10]]}},"alternative-id":["10.1145\/3360591"],"URL":"https:\/\/doi.org\/10.1145\/3360591","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,10]]},"assertion":[{"value":"2019-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}