Publications associées à The PCL Theorem: Transactions cannot be Parallel, Consistent, and Live

When is it safe to run a transactional workload under Read Committed?

The popular isolation level multiversion Read Committed (RC) exchanges some of the strong guarantees of serializability for increased transaction throughput. Nevertheless, transaction workloads can sometimes be executed under RC while still guaranteeing se ...

ASSOC COMPUTING MACHINERY2023

One-shot Garbage Collection for In-memory OLTP through Temporality-aware Version Storage

Anastasia Ailamaki, Angelos Christos Anadiotis, Periklis Chrysogelos, Syed Mohammad Aunn Raza

Most modern in-memory online transaction processing (OLTP) engines rely on multi-version concurrency control (MVCC) to provide data consistency guarantees in the presence of conflicting data accesses. MVCC improves concurrency by generating a new version o ...

ACM2023

Deciding Robustness for Lower SQL Isolation Levels

Christoph Koch, Bas Ketsman

While serializability always guarantees application correctness, lower isolation levels can be chosen to improve transaction throughput at the risk of introducing certain anomalies. A set of transactions is robust against a given isolation level if every p ...

ASSOC COMPUTING MACHINERY2022

Robustness against Read Committed for Transaction Templates

Christoph Koch, Bas Ketsman

The isolation level Multiversion Read Committed (RC), offered by many database systems, is known to trade consistency for increased transaction throughput. Sometimes, transaction workloads can be safely executed under RC obtaining the perfect isolation of ...

ASSOC COMPUTING MACHINERY2021

Efficient Protocols for Enforcing Causal Consistency in Geo-Replicated Key-Value Data Stores

Kristina Spirovska

Modern large-scale data platforms manage colossal amount of data, generated by the ever-increasing number of concurrent users. Geo-replicated and sharded key-value data stores play a central role when building such platforms. As the strongest consistency m ...

EPFL2020

Deciding Robustness for Lower SQL Isolation Levels

Christoph Koch, Bas Ketsman

While serializability always guarantees application correctness, lower isolation levels can be chosen to improve transaction throughput at the risk of introducing certain anomalies. A set of transactions is robust against a given isolation level if every p ...

ASSOC COMPUTING MACHINERY2020

Task scheduling for highly concurrent analytical and transaction workloads

Anastasia Ailamaki, Iraklis Psaroudakis

Systems and method for a task scheduler with dynamic adjustment of concurrency levels and task granularity are disclosed for improved execution of highly concurrent analytical and transactional systems. The task scheduler can avoid both over commitment and ...

2020

PaRiS: Causally Consistent Transactions with Non-blocking Reads and Partial Replication

Willy Zwaenepoel, Kristina Spirovska, Diego Didona

Geo-replicated data platforms are the backbone of several large-scale online services. Transactional Causal Consistency (TCC) is an attractive consistency level for building such platforms. TCC avoids many anomalies of eventual consistency, eschews the syn ...

IEEE COMPUTER SOC2019

PaRiS: Causally Consistent Transactions with Non-blocking Reads and Partial Replication

Willy Zwaenepoel, Kristina Spirovska, Diego Didona

Geo-replicated data platforms are at the backbone of several large-scale online services. Transactional Causal Consistency (TCC) is an attractive consistency level for building such platforms. TCC avoids many anomalies of eventual consistency, eschews the ...

2019

Fast General Distributed Transactions with Opacity

Aleksandar Dragojevic, Stanko Novakovic, Georgios Chatzopoulos

Transactions can simplify distributed applications by hiding data distribution, concurrency, and failures from the application developer. Ideally the developer would see the abstraction of a single large machine that runs transactions sequentially and neve ...

ASSOC COMPUTING MACHINERY2019

Distributed Transactional Systems Cannot Be Fast

Rachid Guerraoui, Willy Zwaenepoel, Panagiota Fatourou, Junxiong Wang, Diego Didona

We prove that no fully transactional system can provide fast read transactions (including read-only ones that are considered the most frequent in practice). Specifically, to achieve fast read transactions, the system has to give up support of transactions ...

2019

Locking Timestamps versus Locking Objects

Rachid Guerraoui, Tudor Alexandru David, Junxiong Wang

We present multiversion timestamp locking (MVTL), a new genre of multiversion concurrency control algorithms for serializable transactions. The key idea behind MVTL is simple: lock individual timestamps instead of locking objects. After presenting a generi ...

ASSOC COMPUTING MACHINERY2018

Wren: Nonblocking Reads in a Partitioned Transactional Causally Consistent Data Store

Willy Zwaenepoel, Kristina Spirovska, Diego Didona

Transactional Causal Consistency (TCC) extends causal consistency, the strongest consistency model compatible with availability, with interactive read-write transactions, and is therefore particularly appealing for geo-replicated platforms. This paper pres ...

2018

Reliability Mechanisms for Controllers in Real-Time Cyber-Physical Systems

Maaz Mashood Mohiuddin

Cyber-physical systems (CPSs) are real-world processes that are controlled by computer algorithms. We consider CPSs where a centralized, software-based controller maintains the process in a desired state by exchanging measurements and setpoints with proces ...

EPFL2018

Universally Scalable Concurrent Data Structures

Tudor Alexandru David

The increase in the number of cores in processors has been an important trend over the past decade. In order to be able to efficiently use such architectures, modern software must be scalable: performance should increase proportionally to the number of all ...

EPFL2017

Program Analysis and Compilation Techniques for Speeding up Transactional Database Workloads

Mohammad Dashti Rahmat Abadi

There is a trend towards increased specialization of data management software for performance reasons. The improved performance not only leads to a more efficient usage of the underlying hardware and cuts the operation costs of the system, but also is a ga ...

EPFL2017

Optimistic Concurrency with OPTIK

Rachid Guerraoui, Vasileios Trigonakis

We introduce OPTIK, a new practical design pattern for designing and implementing fast and scalable concurrent data structures. OPTIK relies on the commonly-used technique of version numbers for detecting conflicting concurrent operations. We show how to i ...

ACM Press2016

Safety, Liveness and Parallelism in Concurrent Computing

Victor Bushkov

The correctness of a shared object, which can be accessed by several processes concurrently, is specified through two different kinds of properties - safety and liveness. When implementing a shared object it is important to specify its correctness in a suc ...

EPFL2015

Applying HTM to an OLTP System: No Free Lunch

Anastasia Ailamaki, Pinar Tözün, Danica Porobic, David Cervini

Transactional memory is a promising way for implementing efficient synchronization mechanisms for multicore processors. Intel's introduction of hardware transactional memory (HTM) into their Haswell line of processors marks an important step toward mainstr ...

2015

Techniques for Detection, Root Cause Diagnosis, and Classification of In-Production Concurrency Bugs

Baris Can Cengiz Kasikci

Concurrency bugs are at the heart of some of the worst bugs that plague software. Concurrency bugs slow down software development because it can take weeks or even months before developers can identify and fix them. In-production detection, root cause ...

EPFL2015