The PCL Theorem. Transactions cannot be Parallel, Consistent and Live

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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 ...

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 ...

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 ...

We establish a theorem called the PCL theorem, which states that it is impossible to design a transactional memory algorithm that ensures (1) parallelism, i.e., transactions do not need to synchronize unless they access the same application objects, (2) ve ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

Most existing distributed systems use logical clocks to order events in the implementation of various consistency models. Although logical clocks are straightforward to implement and maintain, they may affect the scalability, availability, and latency of t ...

Clock-SI is a fully distributed protocol that implements snapshot isolation (SI) for partitioned data stores. It derives snapshot and commit timestamps from loosely synchronized clocks, rather than from a centralized timestamp authority as used in current ...

Transactional memory (TM) has shown potential to simplify the task of writing concurrent programs. Inspired by classical work on databases, formal definitions of the semantics of TM executions have been proposed. Many of these definitions assumed that acce ...

The shift to multi-core hardware brings new challenges to database systems, as the software parallelism determines performance. Even though database systems traditionally accommodate simultaneous requests, a multitude of synchronization barriers serialize ...

Transactional memory (TM) is perceived as an appealing alternative to critical sections for general purpose concurrent programming. Despite the large amount of recent work on TM implementations, however, very little effort has been devoted to precisely def ...

The deferred update technique is a widely used approach for building replicated database systems. Its fame stems from the fact that read-only transactions can execute locally to any single database replica, providing good performance for workloads where tr ...

In this paper, we study the problem of partial database replication. Numerous previous works have investigated database replication, however, most of them focus on full replication. We are here interested in genuine partial replication protocols, which req ...

The PCL Theorem. Transactions cannot be Parallel, Consistent and Live

Chat with Graph Search

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

Deciding Robustness for Lower SQL Isolation Levels

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

Deciding Robustness for Lower SQL Isolation Levels

The PCL Theorem: Transactions cannot be Parallel, Consistent, and Live

Fast General Distributed Transactions with Opacity

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

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

Distributed Transactional Systems Cannot Be Fast

Locking Timestamps versus Locking Objects

Universally Scalable Concurrent Data Structures

Program Analysis and Compilation Techniques for Speeding up Transactional Database Workloads

Safety, Liveness and Parallelism in Concurrent Computing

Consistency Models in Distributed Systems with Physical Clocks

Clock-SI: Snapshot Isolation for Partitioned Data Stores Using Loosely Synchronized Clocks

Transactions in the Jungle

Aether: A scalable approach to logging

On the Correctness of Transactional Memory

A formal analysis of the deferred update technique

Optimistic Algorithms for Partial Database Replication