Write a Blog >>
SPLASH 2019
Sun 20 - Fri 25 October 2019 Athens, Greece
Wed 23 Oct 2019 15:07 - 15:30 at Olympia - Testing Chair(s): Stephen Kell

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.

Wed 23 Oct

Displayed time zone: Beirut change

14:00 - 15:30
Testing OOPSLA at Olympia
Chair(s): Stephen Kell University of Kent
14:00
22m
Talk
Reflection-Aware Static Regression Test Selection
OOPSLA
August Shi University of Illinois at Urbana-Champaign, Milica Hadzi-Tanovic Technische Universitat Munchen, Lingming Zhang The University of Texas at Dallas, Darko Marinov University of Illinois at Urbana-Champaign, Owolabi Legunsen University of Illinois at Urbana-Champaign
DOI
14:22
22m
Talk
Trace Aware Random Testing for Distributed Systems
OOPSLA
Burcu Kulahcioglu Ozkan Max Planck Institute for Software Systems (MPI-SWS), Rupak Majumdar Max Planck Institute for Software Systems (MPI-SWS), Simin Oraee Max Planck Institute for Software Systems (MPI-SWS)
DOI
14:45
22m
Talk
Automatic and Scalable Detection of Logical Errors in Functional Programming Assignments
OOPSLA
Dowon Song Korea University, Myungho Lee Korea University, Hakjoo Oh Korea University
DOI
15:07
22m
Talk
On the Complexity of Checking Transactional Consistency
OOPSLA
Ranadeep Biswas IRIF, University Paris Diderot & CNRS, Constantin Enea IRIF, University Paris Diderot & CNRS
DOI