On the complexity of checking transactional consistency
Authors:
Open Access
- 10 October 2019
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 3 (OOPSLA) , 1-28
Abstract
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.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Replicated data types2014
- Dynamic partial-order reduction for model checking software2005
- An Extensible SAT-solver2004
- Session guarantees for weakly consistent replicated data2002
- Testing Shared MemoriesSIAM Journal on Computing, 1997
- A critique of ANSI SQL isolation levels1995
- Trace theory1987
- Expressing interesting properties of programs in propositional temporal logic1986
- The serializability of concurrent database updatesJournal of the ACM, 1979
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978