Write a Blog >>
Sun 20 - Fri 25 October 2019 Athens, Greece
Wed 23 Oct 2019 15:07 - 15:30 at Olympia - Testing

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.

This program is tentative and subject to change.

Wed 23 Oct

14:00 - 15:30: OOPSLA - Testing at Olympia
splash-2019-oopsla14:00 - 14:22
August ShiUniversity of Illinois at Urbana-Champaign, Milica Hadzi-TanovicTechnische Universitat Munchen, Lingming ZhangThe University of Texas at Dallas, Darko MarinovUniversity of Illinois at Urbana-Champaign, Owolabi LegunsenUniversity of Illinois at Urbana-Champaign
splash-2019-oopsla14:22 - 14:45
Burcu Kulahcioglu OzkanMax Planck Institute for Software Systems (MPI-SWS), Rupak MajumdarMax Planck Institute for Software Systems (MPI-SWS), Simin OraeeMax Planck Institute for Software Systems (MPI-SWS)
splash-2019-oopsla14:45 - 15:07
Dowon SongKorea University, Myungho LeeKorea University, Hakjoo OhKorea University
splash-2019-oopsla15:07 - 15:30
Ranadeep BiswasIRIF, University Paris Diderot & CNRS, Constantin EneaIRIF, University Paris Diderot & CNRS