Publication
Theory of Transactional Memory
Related publications (83)
One-shot Garbage Collection for In-memory OLTP through Temporality-aware Version Storage
Anastasia Ailamaki, Periklis Chrysogelos, Angelos Christos Anadiotis, 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 ...
ACM2023The splay-list: a distribution-adaptive concurrent skip-list
Amirkeivan Mohtashami, Dan Alistarh
The design and implementation of efficient concurrent data structures has seen significant attention. However, most of this work has focused on concurrent data structures providing good worst-case guarantees, although, in real workloads, objects are often ...
SPRINGER2023Robustness Against Read Committed: A Free Transactional Lunch
Transaction processing is a central part of most database applications. While serializability remains the gold standard for desirable transactional semantics, many database systems offer improved transaction throughput at the expense of introducing potenti ...
ASSOC COMPUTING MACHINERY2022Efficient Multi-Word Compare and Swap
Rachid Guerraoui, Mihail Igor Zablotchi
Atomic lock-free multi-word compare-and-swap (MCAS) is a powerful tool for designing concurrent algorithms. Yet, its widespread usage has been limited because lock-free implementations of MCAS make heavy use of expensive compare-and-swap (CAS) instructions ...
Schloss Dagstuhl, Leibniz-Zentrum2020Fast 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 MACHINERY2019Distributed Transactional Systems Cannot Be Fast
Rachid Guerraoui, Willy Zwaenepoel, Diego Didona, Junxiong Wang, Panagiota Fatourou
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 ...
2019The PCL Theorem: Transactions cannot be Parallel, Consistent, and Live
Rachid Guerraoui, Victor Bushkov, Panagiota Fatourou
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 ...
ASSOC COMPUTING MACHINERY2019The Complexity of Reliable and Secure Distributed Transactions
The use of transactions in distributed systems dates back to the 70's. The last decade has also seen the proliferation of transactional systems. In the existing transactional systems, many protocols employ a centralized approach in executing a distributed ...
EPFL2018Locking Timestamps versus Locking Objects
Rachid Guerraoui, Junxiong Wang, Tudor Alexandru David
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 MACHINERY2018Scalable Synchronization in Shared-Memory Systems: Extrapolating, Adapting, Tuning
As hardware evolves, so do the needs of applications. To increase the performance of an application,
there exist two well-known approaches. These are scaling up an application, using a larger multi-core
platform, or scaling out, by distributing work to mul ...
EPFL2018