On obstruction-free transactions

ABSTRACT

This paper studies obstruction-free software transactional memory systems (OFTMs). These systems are appealing, for they combine the atomicity property of transactions with a liveness property that ensures the commitment of every transaction that eventually encounters no contention.

We precisely define OFTMs and establish two of their fundamental properties. First, we prove that the consensus number of such systems is 2. This indicates that OFTMs cannot be implemented with plain read/write shared memory, on the one hand, but, on the other hand, do not require powerful universal objects, such as compare-and-swap. Second, we prove that OFTMs cannot ensure disjoint-access-parallelism (in a strict sense). This may result in artificial "hot spots" and thus limit the performance of OFTMs.

REFERENCES

• 1: RSTM--the Rochester software transactional memory runtime. http://www.cs.rochester.edu/research/synchronization/rstm.
• 2: Yehuda Afek , Michael Merritt , Gadi Taubenfeld, The power of multi-objects (extended abstract), Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.213-222, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248096]
• 3: Yehuda Afek , Michael Merritt , Gadi Taubenfeld , Dan Touitou, Disentangling multi-object operations (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.111-120, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259431]
• 4: Marcos K. Aguilera , Svend Frolund , Vassos Hadzilacos , Stephanie L. Horn , Sam Toueg, Abortable and query-abortable objects and their efficient implementation, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281107]
• 5: Hagit Attiya , Rachid Guerraoui , Danny Hendler , Petr Kouznetsov, Synchronizing without locks is inherently expensive, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146427]
• 6: H. Attiya, R. Guerraoui, and P. Kouznetsov. Computing with reads and writes in the absence of step contention. In Proceedings of the 19th International Symposium on Distributed Computing (DISC), 2005.
• 7: H. Attiya and E. Hillel. Built-in coloring for highly-concurrent doubly-linked lists. In Proceedings of the 20th International Symposium on Distributed Computing (DISC), 2006.
• 8: J. Cachopo and A. Rito-Silva. Versioned boxes as the basis for memory transactions. In Proceedings of the Workshop on Synchronization and Concurrency in Object-Oriented Languages (SCOOL), 2005.
• 9: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 10: D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In Proceedings of the 20th International Symposium on Distributed Computing (DISC), 2006.
• 11: D. Dice and N. Shavit. What really makes transactions fast? In Proceedings of the 1st ACM SIGPLAN Workshop on Transactional Computing (TRANSACT), 2006.
• 12: R. Ennals. Software transactional memory should not be obstruction-free. Technical Report IRC-TR--06--052, Intel Research Cambridge Tech Report, Jan 2006.
• 13: Pascal Felber , Christof Fetzer , Torvald Riegel, Dynamic performance tuning of word-based software 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.1345241]
• 14: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 15: R. Guerraoui and M. Kapalka. On obstruction-free transactions. Technical report, EPFL, 2008.
• 16: 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]
• 17: 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]
• 18: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 19: 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]
• 20: Maurice Herlihy , Victor Luchangco , Mark Moir, Obstruction-Free Synchronization: Double-Ended Queues as an Example, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.522, May 19-22, 2003
• 21: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 22: 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]
• 23: 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]
• 24: Prasad Jayanti, Robust wait-free hierarchies, Journal of the ACM (JACM), v.44 n.4, p.592-614, July 1997 [doi>10.1145/263867.263888]
• 25: J. R. Larus and R. Rajwar. Transactional Memory. Morgan & Claypool, 2007.
• 26: V. J. Maranthe, W. N. Scherer III, and M. L. Scott. Adaptive software transactional memory. In Proceedings of the 19th International Symposium on Distributed Computing (DISC), pages 354--368, 2005.
• 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: Eric Ruppert, Consensus numbers of multi-objects, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.211-217, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277736]
• 29: 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]
• 30: F. Tabba, C. Wang, J. R. Goodman, and M. Moir. NZTM: nonblocking zero-indirection transactional memory. In Proceedings of the 2nd ACM SIGPLAN Workshop on Transactional Computing (TRANSACT), 2007.

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, Theory

Keywords:
consensus number, impossibility, obstruction-freedom, transactional memory