ON THE INPUT ACCEPTANCE OF TRANSACTIONAL MEMORY
Abstract
We present the Input Acceptance of Transactional Memory (TM). Despite the large interest for performance of TMs, no existing research work has investigated the impact of solving a conflict that does not need to be solved. Traditional solutions for a TM to be correct is to delay or abort a transaction as soon as it presents a risk to violate consistency. Both alternatives are costly and should be avoided if consistency is actually preserved. To address this problem, we introduce the input acceptance of a TM as its ability to commit transactions, we upper-bound the input acceptance of existing TMs and propose a new TM with higher input acceptance.
Part of this work already appeared in the 12th International Conference On Principles Of DIstributed Systems [6]. This work is partially supported by the Velox Project ICT-216852 and the Swiss National Foundation Grant 200021-118043.
References
-
Utku Aydonat and Tarek S. Abdelrahman , Serializability of transactions in software transactional memory , TRANSACT '08: 3rd ACM SIGPLAN Workshop on Transactional Computing . Google Scholar -
Philip A. Bernstein , Vassos Hadzilacos and Nathan Goodman , Concurrency Control and Recovery in Database Systems ( Addison-Wesley , 1987 ) . Google Scholar - Dave Dice, Ori Shalev, and Nir Shavit. Transactional locking II. In DISC '06: Proceedings of the 20th International Symposium on Distributed Computing, volume 4167 of LNCS, pages 194–208. Springer, 2006 . Google Scholar
Pascal Felber , Torvald Riegel and Christof Fetzer , Dynamic performance tuning of word-based software transactional memory, PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (ACM, 2008) pp. 237–246. Google Scholar- IEEE Trans. on Knowl. and Data Eng. 4(6), 509 (1992), DOI: 10.1109/69.180602. Crossref, ISI, Google Scholar
- Vincent Gramoli, Derin Harmanci, and Pascal Felber. Toward a theory of input acceptance for transactional memories. In OPODIS '08: Proceedings of the 12th International Conference on Principles of Distributed Systems, volume 5401 of LNCS, pages 527–533, 2008 . Google Scholar
- Rachid Guerraoui, Thomas Henzinger, and Vasu Singh. Permissiveness in transactional memories. In DISC '08: Proceedings of the 22nd International Symposium on Distributed Computing, volume 5218 of LNCS, pages 305–319, 2008 . Google Scholar
- Rachid Guerraoui, Maurice Herlihy, and Bastian Pochon. Polymorphic contention management. In DISC '05: Proceedings of the 19th International Symposium on Distributed Computing, volume 3724 of LNCS, pages 303–323. Springer, 2005 . Google Scholar
Rachid Guerraoui and Michał Kapałka , On the correctness of transactional memory, PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (ACM, 2008) pp. 175–184. Google Scholar- SIGPLAN Not. 38(11), 388 (2003), DOI: 10.1145/949343.949340. Crossref, ISI, Google Scholar
Maurice Herlihy , Software transactional memory for dynamic-sized data structures, PODC '03: Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (2003) pp. 92–101. Google Scholar- ACM Trans. Program. Lang. Syst. 12(3), 463 (1990), DOI: 10.1145/78969.78972. Crossref, ISI, Google Scholar
- Jeff Napper and Lorenzo Alvisi. Lock-free serializable transactions. Technical Report TR-05-04, Department of Computer Sciences, University of Texas at Austin, 2005 . Google Scholar
- J. ACM 26(4), 631 (1979), DOI: 10.1145/322154.322158. Crossref, ISI, Google Scholar
-
Cristian Perfumo , Dissecting transactional executions in haskell , TRANSACT '07: 2nd ACM SIGPLAN Workshop on Transactional Computing ( 2007 ) . Google Scholar Torval Riegel , From causal to z-linearizable transactional memory, PODC '07: Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (ACM, New York, NY, USA, 2007) pp. 340–341. Google Scholar- J. ACM 31(2), 227 (1984), DOI: 10.1145/62.322425. Crossref, ISI, Google Scholar


