Brief announcement: concurrent non-commutative boosted transactions

ABSTRACT

Transactional boosting is a methodology which improves transaction performance by using data-structure commutativity and abstract locks for synchronization.

We announce a method for concurrent execution of non-commuting operations from distinct boosted transactions. Abstract locks are passed from one transaction to the next, and dependencies are created, enforcing certain commit orders. We summarize the approach and describe novel techniques for (i) performing recovery lazily and (ii) detecting cyclic dependencies.

REFERENCES

• 1: B. R. Badrinath , Krithi Ramamritham, Semantics-based concurrency control: beyond commutativity, ACM Transactions on Database Systems (TODS), v.17 n.1, p.163-199, March 1992 [doi>10.1145/128765.128771]
• 2: Broder, A., and Mitzenmacher, M. Network Applications of Bloom Filters: A Survey. Internet Mathematics 1, 4 (2004).
• 3: Maurice Herlihy , Eric Koskinen, Transactional boosting: a methodology for highly-concurrent transactional objects, 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.1345237]
• 4: Eric Koskinen , Maurice Herlihy, Dreadlocks: efficient deadlock detection, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378585]
• 5: C. Mohan , Don Haderle , Bruce Lindsay , Hamid Pirahesh , Peter Schwarz, ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging, ACM Transactions on Database Systems (TODS), v.17 n.1, p.94-162, March 1992 [doi>10.1145/128765.128770]
• 6: Hany E. Ramadan , Indrajit Roy , Maurice Herlihy , Emmett Witchel, Committing conflicting transactions in an STM, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
commutativity, cyclic dependency, lazy recovery, transactional boosting, transactional memory