Inherent limitations on disjoint-access parallel implementations of transactional memory

ABSTRACT

Transactional memory (TM) is a promising approach for designing concurrent data structures, and it is essential to develop better understanding of the formal properties that can be achieved by TM implementations. Two fundamental properties of TM implementations are disjoint-access parallelism, which is critical for their scalability, and the invisibility of read operations, which reduces memory contention.

This paper proves an inherent tradeoff for implementations of transactional memories: they cannot be both disjoint-access parallel and have read-only transactions that are invisible and always terminate successfully. In fact, a lower bound of Ω(t) is proved on the number of writes needed in order to implement a read-only transaction of t items, which successfully terminates in a disjoint-access parallel TM implementation. The results assume strict serializability and thus hold under the assumption of opacity. It is shown how to extend the results to hold also for weaker consistency conditions, serializability and snapshot isolation.

REFERENCES

• 1: Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993 [doi>10.1145/153724.153741]
• 2: H. Attiya, F. Ellen, and P. Fatourou. The complexity of updating multi-writer snapshot objects. In ICDCN '06, pages 319--330.
• 3: Hagit Attiya , Rachid Guerraoui , Eric Ruppert, Partial snapshot objects, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378591]
• 4: Hillel Avni , Nir Shavit, Maintaining Consistent Transactional States without a Global Clock, Proceedings of the 15th international colloquium on Structural Information and Communication Complexity, June 17-20, 2008, Villars-sur-Ollon, Switzerland [doi>10.1007/978-3-540-69355-0_12]
• 5: U. Aydonat and T. Abdelrahman. Serializability of transactions in software transactional memory. In TRANSACT '08.
• 6: D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In DISC '06, pages 194--208.
• 7: Vincent Gramoli , Derin Harmanci , Pascal Felber, Toward a Theory of Input Acceptance for Transactional Memories, Proceedings of the 12th International Conference on Principles of Distributed Systems, December 15-18, 2008, Luxor, Egypt [doi>10.1007/978-3-540-92221-6_33]
• 8: Rachid Guerraoui , Thomas A. Henzinger , Vasu Singh, Permissiveness in Transactional Memories, Proceedings of the 22nd international symposium on Distributed Computing, September 22-24, 2008, Arcachon, France [doi>10.1007/978-3-540-87779-0_21]
• 9: Rachid Guerraoui , Michal Kapalka, On obstruction-free transactions, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378587]
• 10: Rachid Guerraoui , Michal Kapalka, On the correctness of transactional memory, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345233]
• 11: Rachid Guerraoui , Michal Kapalka, The semantics of progress in lock-based transactional memory, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
• 12: Timothy L. Harris , Keir Fraser , Ian A. Pratt, A Practical Multi-word Compare-and-Swap Operation, Proceedings of the 16th International Conference on Distributed Computing, p.265-279, October 28-30, 2002
• 13: Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872048]
• 14: M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2008.
• 15: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 16: Damien Imbs , Michel Raynal, A Lock-Based STM Protocol That Satisfies Opacity and Progressiveness, Proceedings of the 12th International Conference on Principles of Distributed Systems, December 15-18, 2008, Luxor, Egypt [doi>10.1007/978-3-540-92221-6_16]
• 17: Amos Israeli , Lihu Rappoport, Disjoint-access-parallel implementations of strong shared memory primitives, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.151-160, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198079]
• 18: Amos Israeli , Asaf Shirazi, The time complexity of updating snapshot memories, Information Processing Letters, v.65 n.1, p.33-40, Jan 1, 1998 [doi>10.1016/S0020-0190(97)00189-0]
• 19: Shiyong Lu , Arthur Bernstein , Philip Lewis, Correct Execution of Transactions at Different Isolation Levels, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1070-1081, September 2004 [doi>10.1109/TKDE.2004.34]
• 20: J. Napper and L. Alvisi. Lock-free serializable transactions. Technical Report TR-05-04, The University of Texas at Austin, 2005.
• 21: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
• 22: T. Riegel, P. Felber, and C. Fetzer. A lazy snapshot algorithm with eager validation. In DISC '06, pages 284--298.
• 23: T. Riegel, C. Fetzer, and P. Felber. Snapshot isolation for software transactional memory. In TRANSACT '06.
• 24: Torval Riegel , Christof Fetzer , Heiko Sturzrehm , Pascal Felber, From causal to z-linearizable transactional memory, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281162]
• 25: Gerhard Weikum , Gottfried Vossen, Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Design, Theory

Keywords:
disjoint-access parallelism, impossibility result, lower bound, partial snapshots, transactional memory