World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

ON THE INPUT ACCEPTANCE OF TRANSACTIONAL MEMORY

    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
    • H. Garcia-Molina and K. Salem, IEEE Trans. on Knowl. and Data Eng. 4(6), 509 (1992), DOI: 10.1109/69.180602. Crossref, ISIGoogle 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
    • Tim Harris and Keir Fraser, SIGPLAN Not. 38(11), 388 (2003), DOI: 10.1145/949343.949340. Crossref, ISIGoogle Scholar
    • Maurice Herlihyet al., 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
    • Maurice Herlihy and Jeannette M. Wing, ACM Trans. Program. Lang. Syst. 12(3), 463 (1990), DOI: 10.1145/78969.78972. Crossref, ISIGoogle 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
    • Christos H. Papadimitriou, J. ACM 26(4), 631 (1979), DOI: 10.1145/322154.322158. Crossref, ISIGoogle Scholar
    • Cristian   Perfumo et al. , Dissecting transactional executions in haskell , TRANSACT '07: 2nd ACM SIGPLAN Workshop on Transactional Computing ( 2007 ) . Google Scholar
    • Torval Riegelet al., 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
    • Mihalis Yannakakis, J. ACM 31(2), 227 (1984), DOI: 10.1145/62.322425. Crossref, ISIGoogle Scholar