Hagit Attiya
Eshcar Hillel
ABSTRACT
Transactional memory (TM) is a promising approach for designing concurrent data structures, and it is essential to develop better understanding of the formal properties that can be achieved by TM implementations. Two fundamental properties of TM implementations are disjoint-access parallelism, which is critical for their scalability, and the invisibility of read operations, which reduces memory contention.
This paper proves an inherent tradeoff for implementations of transactional memories: they cannot be both disjoint-access parallel and have read-only transactions that are invisible and always terminate successfully. In fact, a lower bound of Ω(t) is proved on the number of writes needed in order to implement a read-only transaction of t items, which successfully terminates in a disjoint-access parallel TM implementation. The results assume strict serializability and thus hold under the assumption of opacity. It is shown how to extend the results to hold also for weaker consistency conditions, serializability and snapshot isolation.
- Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. Atomic snapshots of shared memory. J. ACM, 40(4):873--890, 1993. Google Scholar
Digital Library
- H. Attiya, F. Ellen, and P. Fatourou. The complexity of updating multi-writer snapshot objects. In ICDCN '06, pages 319--330.Google Scholar
- H. Attiya, R. Guerraoui, and E. Ruppert. Partial snapshot objects. In SPAA '08, pages 336--343. Google ScholarDigital Library
- H. Avni and N. Shavit. Maintaining consistent transactional states without a global clock. In SIROCCO '08, pages 131--140. Google ScholarDigital Library
- U. Aydonat and T. Abdelrahman. Serializability of transactions in software transactional memory. In TRANSACT '08.Google Scholar
- D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In DISC '06, pages 194--208.Google Scholar
- V. Gramoli, D. Harmanci, and P. Felber. Towards a theory of input acceptance for transactional memories. In OPODIS '08, pages 527--533. Google ScholarDigital Library
- R. Guerraoui, T. A. Henzinger, and V. Singh. Permissiveness in transactional memories. In DISC '08. Google ScholarDigital Library
- R. Guerraoui and M. Kapalka. On obstruction-free transactions. In SPAA '08, pages 304--313. Google ScholarDigital Library
- R. Guerraoui and M. Kapalka. On the correctness of transactional memory. In PPoPP '08, pages 175--184. Google ScholarDigital Library
- R. Guerraoui and M. Kapalka. The semantics of progress in lock-based transactional memory. In POPL '09, pages 404--415. Google ScholarDigital Library
- T. L. Harris, K. Fraser, and I. A. Pratt. A practical multi-word compare-and-swap operation. In DISC '02, pages 265--279. Google ScholarDigital Library
- M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer III. Software transactional memory for dynamic-sized data structures. In PODC '03, pages 92--101. Google ScholarDigital Library
- M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2008. Google ScholarDigital Library
- M. P. Herlihy and J. M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463--492, 1990. Google ScholarDigital Library
- D. Imbs and M. Raynal. A lock-based protocol for software transactional memory. In OPODIS '08, pages 226--245. Google ScholarDigital Library
- A. Israeli and L. Rappoport. Disjoint-access-parallel implementations of strong shared memory primitives. PODC '94, pages 151--160. Google ScholarDigital Library
- A. Israeli and A. Shirazi. The time complexity of updating snapshot memories. Inf. Process. Lett., 65(1):33--40, 1998. Google ScholarDigital Library
- S. Lu, A. Bernstein, and P. Lewis. Correct execution of transactions at different isolation levels. IEEE Transactions on Knowledge and Data Engineering, 16(9):1070--1081, 2004. Google ScholarDigital Library
- J. Napper and L. Alvisi. Lock-free serializable transactions. Technical Report TR-05-04, The University of Texas at Austin, 2005.Google Scholar
- C. H. Papadimitriou. The serializability of concurrent database updates. J. ACM, 26(4):631--653, 1979. Google ScholarDigital Library
- T. Riegel, P. Felber, and C. Fetzer. A lazy snapshot algorithm with eager validation. In DISC '06, pages 284--298. Google ScholarDigital Library
- T. Riegel, C. Fetzer, and P. Felber. Snapshot isolation for software transactional memory. In TRANSACT '06.Google Scholar
- T. Riegel, C. Fetzer, H. Sturzrehm, and P. Felber. From causal to z-linearizable transactional memory. In PODC '07, pages 340--341. Google ScholarDigital Library
- G. Weikum and G. Vossen. Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery. Morgan Kaufmann, 2001. Google ScholarDigital Library
Index Terms
- Inherent limitations on disjoint-access parallel implementations of transactional memory
Recommendations
Inherent Limitations on Disjoint-Access Parallel Implementations of Transactional Memory
Special Issue: Parallelism in Algorithms and ArchitecturesTransactional memory (TM) is a popular approach for alleviating the difficulty of programming concurrent applications; TM guarantees that a transaction, consisting of a sequence of operations, appear to be executed atomically. Two fundamental properties ...
Disjoint-Access Parallelism: Impossibility, Possibility, and Cost of Transactional Memory Implementations
PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed ComputingDisjoint-Access Parallelism (DAP) is considered one of the most desirable properties to maximize the scalability of Transactional Memory (TM). This paper investigates the possibility and inherent cost of implementing a DAP TM that ensures two properties ...
Grasping the gap between blocking and non-blocking transactional memories
Transactional memory (TM) is an inherently optimistic abstraction: it allows concurrent processes to execute sequences of shared-data accesses (transactions) speculatively, with an option of aborting them in the future. Early TM designs avoided using ...
Comments