Abstract
Transactional 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 of TM implementations are disjoint-access parallelism and the invisibility of read operations. Disjoint access parallelism ensures that operations on disconnected data do not interfere, and thus it is critical for TM scalability. The invisibility of read operations means that their implementation does not write to the memory, thereby reducing 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, snapshot isolation and serializability.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. Assoc. Comput. Mach. 40(4), 873–890 (1993)
Attiya, H., Ellen, F., Fatourou, P.: The complexity of updating multi-writer snapshot objects. In: Proc. 8th International Conference on Distributed Computing and Networking, pp. 319–330 (2006)
Attiya, H., Guerraoui, R., Ruppert, E.: Partial snapshot objects. In: Proc. 20th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 336–343 (2008)
Avni, H., Shavit, N.: Maintaining consistent transactional states without a global clock. In: Proc. 15th International Colloquium on Structural Information and Communication Complexity, pp. 131–140 (2008)
Aydonat, U., Abdelrahman, T.: Serializability of transactions in software transactional memory. In: 3rd ACM SIGPLAN Workshop on Transactional Computing (2008)
Berenson, H., Bernstein, P., Gray, J., Melton, J., O’Neil, E., O’Neil, P.: A critique of ANSI SQL isolation levels. SIGMOD Rec. 24(2), 1–10 (1995)
Dice, D., Shalev, O., Shavit, N.: Transactional locking II. In: Proc. 20th International Symposium on Distributed Computing, pp. 194–208 (2006)
Gramoli, V., Harmanci, D., Felber, P.: Towards a theory of input acceptance for transactional memories. In: Proc. 13th International Conference on Principle of Distributed Systems, pp. 527–533 (2008)
Guerraoui, R., Kapalka, M.: On obstruction-free transactions. In: Proc. 20th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 304–313 (2008)
Guerraoui, R., Kapalka, M.: On the correctness of transactional memory. In: Proc. 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 175–184 (2008)
Guerraoui, R., Kapalka, M.: The semantics of progress in lock-based transactional memory. In: Proc. 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 404–415 (2009)
Guerraoui, R., Henzinger, T.A., Singh, V.: Permissiveness in transactional memories. In: Proc. 22nd International Symposium on Distributed Computing, pp. 305–319 (2008)
Harris, T.L., Fraser, K., Pratt, I.A.: A practical multi-word compare-and-swap operation. In: Proc. 16th International Symposium on Distributed Computing, pp. 265–279 (2002)
Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann, San Mateo (2008)
Herlihy, M., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)
Herlihy, M., Luchangco, V., Moir, M.: Scherer III W. N.: Software transactional memory for dynamic-sized data structures. In: Proc. 22nd ACM Symposium on Principles of Distributed Computing, pp. 92–101 (2003)
Imbs, D., Raynal, M.: A lock-based protocol for software transactional memory. In: Proc. 13th International Conference on Principle of Distributed Systems, pp. 226–245 (2008)
Imbs, D., Raynal, M.: Help when needed, but no more: efficient read/write partial snapshot. In: Proc. 23nd International Symposium on Distributed Computing, pp. 142–156 (2009)
Imbs, D., Raynal, M., de Mendivil, J.R.: Brief announcement: virtual world consistency: a new condition for STM systems. In: Proc. 28th ACM Symposium on Principles of Distributed Computing, pp. 280–281 (2009)
Israeli, A., Rappoport, L.: Disjoint-access-parallel implementations of strong shared memory primitives. In: Proc. 13th ACM Symposium on Principles of Distributed Computing, pp. 151–160 (1994)
Israeli, A., Shirazi, A.: The time complexity of updating snapshot memories. Inf. Process. Lett. 65(1), 33–40 (1998)
Keidar, I., Perelman, D.: On avoiding spare aborts in transactional memory. In: Proc. 21th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 59–68 (2009)
Lu, S., Bernstein, A., Lewis, P.: Correct execution of transactions at different isolation levels. IEEE Trans. Knowl. Data Eng. 16(9), 1070–1081 (2004)
Napper, J., Alvisi, L.: Lock-free serializable transactions. Technical Report TR-05-04, The University of Texas at Austin (2005)
Papadimitriou, C.H.: The serializability of concurrent database updates. J. Assoc. Comput. Mach. 26(4), 631–653 (1979)
Riegel, T., Felber, P., Fetzer, C.: A lazy snapshot algorithm with eager validation. In: Proc. 20th International Symposium on Distributed Computing, pp. 284–298 (2006)
Riegel, T., Fetzer, C., Felber, P.: Snapshot isolation for software transactional memory. In: 1st ACM SIGPLAN Workshop on Transactional Computing (2006)
Riegel, T., Fetzer, C., Sturzrehm, H., Felber, P.: From causal to z-linearizable transactional memory. In: Proc. 26th ACM Symposium on Principles of Distributed Computing, pp. 340–341 (2007)
Weikum, G., Vossen, G.: Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery. Morgan Kaufmann, San Mateo (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is partially supported by the Israel Science Foundation (grant number 953/06) and Intel Corporation. A. Milani is on leave from Sapienza, Universitá di Roma, supported in part by a fellowship from the Lady Davis Foundation and by a grant Progetto FIRB Italia-Israele RBIN047MH9.
Rights and permissions
About this article
Cite this article
Attiya, H., Hillel, E. & Milani, A. Inherent Limitations on Disjoint-Access Parallel Implementations of Transactional Memory. Theory Comput Syst 49, 698–719 (2011). https://doi.org/10.1007/s00224-010-9304-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-010-9304-5