Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The PCL theorem: transactions cannot be parallel, consistent, and live
Bushkov V., Dziuma D., Fatourou P., Guerraoui R. Journal of the ACM66 (1):1-66,2019.Type:Article
Date Reviewed: Apr 15 2019

Transactional memory is one approach to making highly parallel programming manageable. In such approaches, parallel memory accesses are treated somewhat similarly to transactions in a database system, ideally guaranteeing properties similar to the ACID (atomicity, consistency, isolation, durability) guarantee of relational database systems.

The paper at hand presents minimal properties (called the PCL theorem, where PCL stands for parallel, consistent, and live) that cannot be achieved simultaneously by a transactional memory (TM) algorithm, and hence delineates what is achievable and what is not.

The paper starts with an introduction, explaining informally what a TM algorithm is and which properties an appropriate TM algorithm is supposed to satisfy, that is, some form of consistency and some form of liveness. Several such conditions are discussed, and the remaining layout of the paper is provided.

The next section presents an overview of related work discussing different properties of known TM algorithms and existing results. This is followed by a technical introduction that formally defines the concepts informally used in the previous sections, especially some of the consistency conditions discussed.

The next section is central to the paper: it proves the PCL theorem, which states that it is not possible to find a TM algorithm that is weakly adaptive consistent (a very weak consistency condition), obstruction-free, and c-disjoint-access-parallel (also a weak form of parallelism) if the number of processes exceeds a certain threshold. First, a restricted result is proved, the restriction being that the TM algorithm can simultaneously access only one object. Then the result is generalized to simultaneously accessing n objects. The proof is presented in every detail.

The limits of the PCL theorem are discussed next. It is shown that weakening any of the assumed properties of the TM algorithm (for example, weak adaptive consistency or obstruction-freedom) in obvious ways leads to the existence of TM algorithms satisfying the weakened properties, illustrating that the theorem draws a sharp boundary between the existence and nonexistence of TM algorithms.

The paper closes with a conclusion comparing the PCL theorem to the CAP theorem, which at first glance seems to be a very similar impossibility result also connected to three properties that are not simultaneously achievable. In this comparison, it is argued that partition tolerance and disjoint-access-parallelism are not the same thing; the results are only similar in the sense that three properties are not simultaneously achievable.

The paper is very detailed and the authors do their best to make the detailed proofs accessible via examples and intuitive explanations. Proving that something is impossible is often very complex and hard, and following every detail of the proof can be hard for the reader, too. The fact that all of the details are included is very instructive in itself.

Reviewer:  Markus Wolf Review #: CR146533 (1907-0278)
Bookmark and Share
 
Concurrent Programming (D.1.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Concurrent Programming": Date

Type: Journal
Jul 1 1985
Resources in parallel and concurrent systems
, ACM Press, New York, NY, 1991. Type: Book (9780897914000)
Jun 1 1992
Concurrent programming
Andrews G., Benjamin-Cummings Publ. Co., Inc., Redwood City, CA, 1991. Type: Book (9780805300864)
Jun 1 1994
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy