Transactions are back---but are they the same?

ABSTRACT

Transactions are back in the spotlight! They are emerging in concurrent programming languages under the name of transactional memory (TM). Their new role? Concurrency control on new multi-core processors. From afar they look the same as good ol' database transactions. But are they really?

In this position paper, we reflect about the distinguishing features of these memory transactions with respect to their database cousins.

Disclaimer: By its very nature, this position paper does not try to avoid subjectivity.

REFERENCES

• 1: Martín Abadi , Andrew Birrell , Tim Harris , Michael Isard, Semantics of transactional memory and automatic mutual exclusion, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
• 2: Ali-Reza Adl-Tabatabai , Brian T. Lewis , Vijay Menon , Brian R. Murphy , Bratin Saha , Tatiana Shpeisman, Compiler and runtime support for efficient software transactional memory, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 3: Colin Blundell, E. Christopher Lewis, and Milo M. K. Martin. Deconstructing transactional semantics: The subtleties of atomicity. In Proc. 2005 Workshop on Duplicating, Deconstructing and Debunking, 2005.
• 4: Brian D. Carlstrom , Austen McDonald , Hassan Chafi , JaeWoong Chung , Chi Cao Minh , Christos Kozyrakis , Kunle Olukotun, The Atomos transactional programming language, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 5: Christopher Cole , Maurice Herlihy, Snapshots and software transactional memory, Science of Computer Programming, v.58 n.3, p.310-324, December 2005 [doi>10.1016/j.scico.2005.03.006]
• 6: Enterprise JavaBeans. http://java.sun.com/products/ejb/.
• 7: P. Felber, C. Fetzer, U. Müller, T. Riegel, M. Süsskraut, and H. Sturzrehm. Transactifying applications using an open compiler framework. In TRANSACT'07, August 2007.
• 8: Christof Fetzer , Pascal Felber , Karin Hogstedt, Automatic Detection and Masking of Nonatomic Exception Handling, IEEE Transactions on Software Engineering, v.30 n.8, p.547-560, August 2004 [doi>10.1109/TSE.2004.35]
• 9: Rachid Guerraoui , Riccardo Capobianchi , Agnes Lanusse , Pierre Roux, Nesting Actions through Asynchronous Message Passing: the ACS Protocol, Proceedings of the European Conference on Object-Oriented Programming, p.170-184, June 29-July 03, 1992
• 10: Rachid Guerraoui, Maurice Herlihy, Michal Kapalka, and Bastian Pochon. Robust contention management in software transactional memory. In Proceedings of SCOOL, 2005.
• 11: Rachid Guerraoui , Maurice Herlihy , Bastian Pochon, Toward a theory of transactional contention managers, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073863]
• 12: 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]
• 13: Rachid Guerraoui , Michal Kapalka , Jan Vitek, STMBench7: a benchmark for software transactional memory, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 14: Vassos Hadzilacos, A theory of reliability in database systems, Journal of the ACM (JACM), v.35 n.1, p.121-145, Jan. 1988 [doi>10.1145/42267.42272]
• 15: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 16: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 17: Tim Harris , Mark Plesko , Avraham Shinnar , David Tarditi, Optimizing memory transactions, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 18: 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]
• 19: Maurice Herlihy, The transactional manifesto: software engineering and non-blocking synchronization, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, p.280-280, June 12-15, 2005, Chicago, IL, USA [doi>10.1145/1065010.1065011]
• 20: hibernate. http://www.hibernate.org.
• 21: Jörg Kienzle , Rachid Guerraoui, AOP: Does It Make Sense? The Case of Concurrency and Failures, Proceedings of the 16th European Conference on Object-Oriented Programming, p.37-61, June 10-14, 2002
• 22: Barbara Liskov, Distributed programming in Argus, Communications of the ACM, v.31 n.3, p.300-312, March 1988 [doi>10.1145/42392.42399]
• 23: D. B. Lomet, Process structuring, synchronization, and recovery using atomic actions, Proceedings of an ACM conference on Language design for reliable software, p.128-137, March 28-30, 1977, Raleigh, North Carolina
• 24: Virendra J. Marathe, William N. Scherer III, and Michael L. Scott. Adaptive software transactional memory. In Proceedings of DISC, pages 354--368, 2005.
• 25: Bill McCloskey , Feng Zhou , David Gay , Eric Brewer, Autolocker: synchronization inference for atomic sections, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.346-358, January 11-13, 2006, Charleston, South Carolina, USA
• 26: H. Garcia Molina and K. Salem. Automatic detection and masking of non-atomic exception handling. IEEE Transactions on Knowledge and Data Engineering, 4(6):509--516, 1992.
• 27: 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]
• 28: Torvald Riegel, Pascal Felber, and Christof Fetzer. A Lazy Snapshot Algorithm with Eager Validation. In 20th International Symposium on Distributed Computing (DISC), September 2006.
• 29: Torvald Riegel, Christof Fetzer, and Pascal Felber. Snapshot isolation for software transactional memory. In TRANSACT'06, Jun 2006.
• 30: Torvald Riegel , Christof Fetzer , Pascal Felber, Time-based transactional memory with scalable time bases, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248415]
• 31: William N. Scherer, III , Michael L. Scott, Advanced contention management for dynamic software transactional memory, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073861]
• 32: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 33: Tatiana Shpeisman , Vijay Menon , Ali-Reza Adl-Tabatabai , Steven Balensiefer , Dan Grossman , Richard L. Hudson , Katherine F. Moore , Bratin Saha, Enforcing isolation and ordering in STM, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 34: Michael F. Spear , Virendra J. Marathe , Luke Dalessandro , Michael L. Scott, Privatization techniques for software 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.1281161]
• 35: Andy Wellings , Alan Burns, Implementing Atomic Actions in Ada 95, IEEE Transactions on Software Engineering, v.23 n.2, p.107-123, February 1997 [doi>10.1109/32.585500]

INDEX TERMS

Primary Classification:
  A. General Literature
  A.m MISCELLANEOUS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

General Terms:
Theory