  Modern applications, such as social networking systems and e-commerce
platforms are centered around using large-scale databases for storing and
retrieving data. Accesses to the database are typically enclosed in
transactions that allow computations on shared data to be isolated from other
concurrent computations and resilient to failures. Modern databases trade
isolation for performance. The weaker the isolation level is, the more
behaviors a database is allowed to exhibit and it is up to the developer to
ensure that their application can tolerate those behaviors.
  In this work, we propose stateless model checking algorithms for studying
correctness of such applications that rely on dynamic partial order reduction.
These algorithms work for a number of widely-used weak isolation levels,
including Read Committed, Causal Consistency, Snapshot Isolation, and
Serializability. We show that they are complete, sound and optimal, and run
with polynomial memory consumption in all cases. We report on an implementation
of these algorithms in the context of Java Pathfinder applied to a number of
challenging applications drawn from the literature of distributed systems and
databases.
