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

Abstract

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.

References

1. Yehuda Afek, Dalia Dauber, and Dan Touitou. 1995. Wait-free made fast. In Proceedings of ACM STOC--95.
2. Yehuda Afek, Michael Merritt, Gadi Taubenfeld, and Dan Touitou. 1997. Disentangling multi-object operations (extended abstract). In Proceedings of ACM PODC--97.
3. Mustaque Ahamad, Rida A. Bazzi, Ranjit John, Prince Kohli, and Gil Neiger. 1993. The power of processor consistency. In Proceedings of ACM SPAA--93.
4. Bowen Alpern and Fred B. Schneider. 1985. Defining liveness. Inform. Process. Lett. 21, 4 (1985).
5. Masoud Saeida Ardekani, Pierre Sutra, and Marc Shapiro. 2011. The impossibility of ensuring snapshot isolation in genuine replicated STMs. In Proceedings of WTTM.
6. Masoud Saeida Ardekani, Pierre Sutra, Marc Shapiro, and Nuno Preguiça. 2013. On the scalability of snapshot isolation. In Euro-Par Parallel Processing. Springer, Berlin.
7. Hagit Attiya and Eyal Dagan. 1996. Universal operations: Unary versus binary. In Proceedings of ACM PODC--96.
8. Hagit Attiya and Panagiota Fatourou. 2015. Disjoint-access parallelism in software transactional memory. In Transactional Memory. Foundations, Algorithms, Tools, and Applications. Springer International Publishing.
9. Hagit Attiya and Eshcar Hillel. 2006. Built-in coloring for highly-concurrent doubly-linked lists. In Proceedings of ACM DISC--06.
10. Hagit Attiya and Eshcar Hillel. 2011. Single-version STMs can be multi-version permissive. In Proceedings of ICDCN--11. Springer-Verlag.
11. Hagit Attiya, Eshcar Hillel, and Alessia Milani. 2009. Inherent limitations on disjoint-access parallel implementations of transactional memory. In Proceedings of ACM SPAA--09.
12. Hagit Attiya, Eshcar Hillel, and Alessia Milani. 2011. Inherent limitations on disjoint-access parallel implementations of transactional memory. Theory Comput. Syst. 49, 4 (2011).
13. Hagit Attiya and Jennifer Welch. 2004. Distributed Computing: Fundamentals, Simulations and Advanced Topics. John Wiley 8 Sons, New Jersey.
14. Greg Barnes. 1993. A method for implementing lock-free shared-data structures. In Proceedings of ACM SPAA--93.
15. Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O--Neil, and Patrick O--Neil. 1995. A critique of ANSI SQL isolation levels. ACM SIGMOD Rec. 24, 2 (1995), 1--10.
16. Philip A. Bernstein, Vassco Hadzilacos, and Nathan Goodman. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley Longman Publishing Co., Inc.
17. Victor Bushkov, Rachid Guerraoui, and Michał Kapałka. 2012. On the liveness of transactional memory. In Proceedings of ACM PODC--12.
18. Ricardo J. Dias, João Seco, and João M. Lourenço. 2010. Snapshot isolation anomalies detection in software transactional memory. In Proceedings of InForum--10.
19. Dave Dice and Nir Shavit. 2006. What really makes transactions faster? In Proceedings of TRANSACT--06.
20. Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, and Corentin Travers. 2012. Universal constructions that ensure disjoint-access parallelism and wait-freedom. In Proceedings of ACM PODC--12.
21. Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, and Corentin Travers. 2016. Universal constructions that ensure disjoint-access parallelism and wait-freedom. Distrib. Comput. 29, 4 (01 Aug. 2016), 251--277.
22. Alan Fekete, Dimitrios Liarokapis, Elizabeth O--Neil, Patrick O--Neil, and Dennis Shasha. 2005. Making snapshot isolation serializable. ACM Trans. Database Syst. 30, 2 (2005).
23. Pascal Felber, Christof Fetzer, and Torvald Riegel. 2008. Dynamic performance tuning of word-based software transactional memory. In Proceedings of PPoPP--08. ACM, 237--246.
24. Keir Fraser and Tim Harris. 2007. Concurrent programming without locks. ACM Trans. Comput. Syst. 25, 2, Article 5 (2007).
25. Kourosh Gharachorloo, Daniel Lenoski, James Laudon, Phillip Gibbons, Anoop Gupta, and John Hennessy. 1990. Memory consistency and event ordering in scalable shared-memory multiprocessors. In Proceedings of ACM ISCA--90. New York, NY, 15--26.
26. Seth Gilbert and Nancy Lynch. 2002. Brewer--s conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News 33, 2 (2002).
27. J. R. Goodman. 1989. Cache Consistency and Sequential Consistency. Technical Report. Technical Report 61, IEEE Scalable Coherent Interface Working Group.
28. Jim Gray. 1980. A transaction model. In Proceedings of ICALP--80. Springer-Verlag.
29. Rachid Guerraoui and Michal Kapalka. 2008. On obstruction-free transactions. In Proceedings of ACM SPAA--08.
30. Rachid Guerraoui and Michal Kapalka. 2008. On the correctness of transactional memory. In Proceedings of ACM PPoPP--08.
31. Rachid Guerraoui and Michal Kapalka. 2009. The semantics of progress in lock-based transactional memory. In Proceedings of POPL--09. ACM, 404--415.
32. Rachid Guerraoui and Michal Kapalka. 2010. Principles of Transactional Memory. Morgan and Claypool.
33. M. Herlihy. 1990. A methodology for implementing highly concurrent data structures. ACM SIGPLAN Not. 25, 3 (1990).
34. Maurice Herlihy. 1991. Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13, 1 (1991).
35. Maurice Herlihy, Victor Luchangco, Mark Moir, and William N. Scherer, III. 2003. Software transactional memory for dynamic-sized data structures. In Proceedings of ACM PODC--03.
36. Maurice Herlihy and J. Eliot B. Moss. 1993. Transactional memory: Architectural support for lock-free data structures. SIGARCH Comput. Architect. News 21, 2 (1993).
37. P. W. Hutto and M. Ahamad. 1990. Slow memory: Weakening consistency to enhance concurrency in distributed shared memories. In Proceedings of ICDCS--90. IEEE, 302--309.
38. Damien Imbs and Michel Raynal. 2010. A versatile STM protocol with invisible read operations that satisfies the virtual world consistency condition. In Proceedings of SIROCCO--09.
39. Amos Israeli and Lihu Rappoport. 1994. Disjoint-access-parallel implementations of strong shared memory primitives. In Proceedings of ACM PODC--94.
40. Petr Kuznetsov and Srivatsan Ravi. 2015. On partial wait-freedom in transactional memory. In Proceedings of ICDCN--15.
41. R. J. Lipton and J. S. Sandberg. 1988. Pram: A Scalable Shared Memory. Technical Report CS-TR-180-88. Princeton University.
42. Heiner Litz, David Cheriton, Amin Firoozshahian, Omid Azizi, and John P. Stevenson. 2014. SI-TM: Reducing transactional memory abort rates through snapshot isolation. In Proceedings of ACM ASPLOS--14. 383--398.
43. Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann Publishers Inc.
44. Virendra J. Marathe, William N. Scherer, and Michael L. Scott. 2005. Adaptive software transactional memory. In Proceedings of DISC--05. Springer-Verlag.
45. Susan Owicki and Leslie Lamport. 1982. Proving liveness properties of concurrent programs. ACM Trans. Program. Lang. Syst. 4, 3 (1982), 455--495.
46. Christos H. Papadimitriou. 1979. The serializability of concurrent database updates. J. ACM 26, 4 (1979).
47. Sebastiano Peluso, Roberto Palmieri, Paolo Romano, Binoy Ravindran, and Francesco Quaglia. 2015. Disjoint-access parallelism: Impossibility, possibility, and cost of transactional memory implementations. In Proceedings of ACM PODC--15.
48. Dmitri Perelman, Rui Fan, and Idit Keidar. 2010. On maintaining multiple versions in STM. In Proceedings of ACM PODC--10.
49. M. Raynal, G. Thia-Kime, and M. Ahamad. 1997. From serializable to causal transactions for collaborative applications. In Proceedings of EUROMICRO--97.
50. Torvald Riegel, Christof Fetzer, and Pascal Felber. 2006. Snapshot isolation for software transactional memory. In Proceedings of ACM TRANSACT--06.
51. Nir Shavit and Dan Touitou. 1995. Software transactional memory. In Proceedings of ACM PODC--95.
52. Fuad Tabba, Mark Moir, James R. Goodman, Andrew W. Hay, and Cong Wang. 2009. NZTM: Nonblocking zero-indirection transactional memory. In Proceedings of ACM SPAA--09.
53. John Turek, Dennis Shasha, and Sundeep Prakash. 1992. Locking without blocking: Making lock based concurrent data structure algorithms nonblocking. In Proceedings of ACM PODS--92.

Index Terms

• Computing methodologies

  • Concurrent computing methodologies

    • Concurrent algorithms