{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T15:53:31Z","timestamp":1783439611247,"version":"3.54.6"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:p>Users who care about their data store it in databases, which (at least in principle) guarantee some form of transactional isolation. However, experience shows that many databases do not provide the isolation guarantees they claim. With the recent proliferation of new distributed databases, demand has grown for checkers that can, by generating client workloads and injecting faults, produce anomalies that witness a violation of a stated guarantee. An ideal checker would be sound (no false positives), efficient (polynomial in history length and concurrency), effective (finding violations in real databases), general (analyzing many patterns of transactions), and informative (justifying the presence of an anomaly with understandable counterexamples). Sadly, we are aware of no checkers that satisfy these goals.<\/jats:p>\n          <jats:p>We present Elle: a novel checker which infers an Adya-style dependency graph between client-observed transactions. It does so by carefully selecting database objects and operations when generating histories, so as to ensure that the results of database reads reveal information about their version history. Elle can detect every anomaly in Adya et al's formalism (except for predicates), discriminate between them, and provide concise explanations of each. This paper makes the following contributions: we present Elle, demonstrate its soundness over specific datatypes, measure its efficiency against the current state of the art, and give evidence of its effectiveness via a case study of four real databases.<\/jats:p>","DOI":"10.14778\/3430915.3430918","type":"journal-article","created":{"date-parts":[[2021,12,9]],"date-time":"2021-12-09T20:12:47Z","timestamp":1639080767000},"page":"268-280","source":"Crossref","is-referenced-by-count":63,"title":["Elle"],"prefix":"10.14778","volume":"14","author":[{"given":"Kyle","family":"Kingsbury","sequence":"first","affiliation":[{"name":"Jepsen"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Alvaro","sequence":"additional","affiliation":[{"name":"UC Santa Cruz"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,12,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/888672"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/846219.847380"},{"key":"e_1_2_1_3_1","unstructured":"Anish Athalye. 2017--2018. Porcupine. https:\/\/github.com\/anishathalye\/porcupine.  Anish Athalye. 2017--2018. Porcupine. https:\/\/github.com\/anishathalye\/porcupine."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/356842.356846"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1979.234182"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360591"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093333.3009895"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3296979.3192415"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1809028.1806634"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28869-2_4"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1620585.1620587"},{"key":"e_1_2_1_12_1","unstructured":"Andrea Cerone Giovanni Bernardi and Alexey Gotsman. 2015. A Framework for Transactional Consistency Models with Atomic Visibility (CONCUR).  Andrea Cerone Giovanni Bernardi and Alexey Gotsman. 2015. A Framework for Transactional Consistency Models with Atomic Visibility (CONCUR)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/357766.351266"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387880.2387905"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087802"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164189"},{"key":"e_1_2_1_17_1","unstructured":"Dgraph Labs. 2020. Dgraph. https:\/\/dgraph.io.  Dgraph Labs. 2020. Dgraph. https:\/\/dgraph.io."},{"key":"e_1_2_1_18_1","unstructured":"Fauna Inc. 2019. FaunaDB. https:\/\/fauna.com.  Fauna Inc. 2019. FaunaDB. https:\/\/fauna.com."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065193"},{"key":"e_1_2_1_20_1","volume-title":"Gecode: Generic Constraint Development Environment. https:\/\/www.gecode.org\/.","author":"Team Gecode","year":"2005"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279614"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_23_1","unstructured":"Kyle Kingsbury. 2013--2019. Knossos. https:\/\/github.com\/jepsen-io\/knossos.  Kyle Kingsbury. 2013--2019. Knossos. https:\/\/github.com\/jepsen-io\/knossos."},{"key":"e_1_2_1_24_1","unstructured":"Kyle Kingsbury. 2016. Gretchen. https:\/\/github.com\/aphyr\/gretchen.  Kyle Kingsbury. 2016. Gretchen. https:\/\/github.com\/aphyr\/gretchen."},{"key":"e_1_2_1_25_1","volume-title":"Elle: Inferring Isolation Anomalies from Experimental Observations. arXiv:2003.10554","author":"Kingsbury Kyle","year":"2020"},{"key":"e_1_2_1_26_1","unstructured":"Kyle Kingsbury and Kit Patella. 2013--2019. Jepsen (Reports). http:\/\/jepsen.io\/analyses.  Kyle Kingsbury and Kit Patella. 2013--2019. Jepsen (Reports). http:\/\/jepsen.io\/analyses."},{"key":"e_1_2_1_27_1","unstructured":"Kyle Kingsbury and Kit Patella. 2013--2019. Jepsen (Software Library). https:\/\/github.com\/jepsen-io\/jepsen.  Kyle Kingsbury and Kit Patella. 2013--2019. Jepsen (Software Library). https:\/\/github.com\/jepsen-io\/jepsen."},{"key":"e_1_2_1_28_1","volume-title":"Testing and Verifying Concurrent Objects. Concurrency and Computation: Practice and Experience 29, 4","author":"Lowe Gavin","year":"2017"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158134"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322158"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1924943.1924961"},{"key":"e_1_2_1_32_1","unstructured":"PingCAP. 2019. TiDB. https:\/\/pingcap.com\/en.  PingCAP. 2019. TiDB. https:\/\/pingcap.com\/en."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/3129633.3129649"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1971.10"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213838"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1993.1015"},{"key":"e_1_2_1_37_1","volume-title":"Weng-Fai Wong, and Meihui Zhang.","author":"Yao Chang","year":"2015"},{"key":"e_1_2_1_38_1","unstructured":"YugaByte Inc. 2019. YugaByte DB. https:\/\/yugabyte.com.  YugaByte Inc. 2019. YugaByte DB. https:\/\/yugabyte.com."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3430915.3430918","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:16:30Z","timestamp":1672222590000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3430915.3430918"}},"subtitle":["inferring isolation anomalies from experimental observations"],"short-title":[],"issued":{"date-parts":[[2020,11]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["10.14778\/3430915.3430918"],"URL":"https:\/\/doi.org\/10.14778\/3430915.3430918","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,11]]}}}