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

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.


Published in:
Journal Of The Acm, 66, 1, 2
Year:
Jan 01 2019
Publisher:
New York, ASSOC COMPUTING MACHINERY
ISSN:
0004-5411
1557-735X
Keywords:
Laboratories:




 Record created 2019-02-12, last modified 2019-06-19


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)