Loading...
research article
The PCL Theorem: Transactions cannot be Parallel, Consistent, and Live
January 1, 2019
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) very little consistency, i.e., a consistency condition, called weak adaptive consistency, introduced here and that is weaker than snapshot isolation, processor consistency, and any other consistency condition stronger than them (such as opacity, serializability, causal serializability, etc.), and (3) very little liveness, i.e., which transactions eventually commit if they run solo.
Type
research article
Web of Science ID
WOS:000457117400002
Authors
Publication date
2019-01-01
Publisher
Published in
Volume
66
Issue
1
Start page
2
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
February 12, 2019
Use this identifier to reference this record