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.


Publié dans:
Journal Of The Acm, 66, 1, 2
Année
Jan 01 2019
Publisher:
New York, ASSOC COMPUTING MACHINERY
ISSN:
0004-5411
1557-735X
Mots-clefs:
Laboratoires:




 Notice créée le 2019-02-12, modifiée le 2020-01-20


Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)