Inherent limitations on disjoint-access parallel implementations of transactional memory. (English) Zbl 1253.68025
Summary: 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 \(\Omega (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.
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 \(\Omega (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.
MSC:
| 68M07 | Mathematical problems of computer architecture |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Keywords:
transactional memory; disjoint-access parallelism; partial snapshots; lower bound; impossibility resultReferences:
| [1] | 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) · Zbl 0783.68029 · doi:10.1145/153724.153741 |
| [2] | 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) · Zbl 1283.68152 |
| [3] | Attiya, H., Guerraoui, R., Ruppert, E.: Partial snapshot objects. In: Proc. 20th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 336–343 (2008) |
| [4] | 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) |
| [5] | Aydonat, U., Abdelrahman, T.: Serializability of transactions in software transactional memory. In: 3rd ACM SIGPLAN Workshop on Transactional Computing (2008) |
| [6] | 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) · doi:10.1145/568271.223785 |
| [7] | Dice, D., Shalev, O., Shavit, N.: Transactional locking II. In: Proc. 20th International Symposium on Distributed Computing, pp. 194–208 (2006) |
| [8] | 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) |
| [9] | Guerraoui, R., Kapalka, M.: On obstruction-free transactions. In: Proc. 20th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 304–313 (2008) |
| [10] | 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) |
| [11] | 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) · Zbl 1315.68065 |
| [12] | Guerraoui, R., Henzinger, T.A., Singh, V.: Permissiveness in transactional memories. In: Proc. 22nd International Symposium on Distributed Computing, pp. 305–319 (2008) · Zbl 1161.68387 |
| [13] | 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) · Zbl 1029.68525 |
| [14] | Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann, San Mateo (2008) |
| [15] | Herlihy, M., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990) · doi:10.1145/78969.78972 |
| [16] | 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) |
| [17] | 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) |
| [18] | 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) · Zbl 1261.68028 |
| [19] | 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) |
| [20] | 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) · Zbl 1373.68102 |
| [21] | Israeli, A., Shirazi, A.: The time complexity of updating snapshot memories. Inf. Process. Lett. 65(1), 33–40 (1998) · Zbl 1339.68022 · doi:10.1016/S0020-0190(97)00189-0 |
| [22] | 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) · Zbl 1320.68055 |
| [23] | Lu, S., Bernstein, A., Lewis, P.: Correct execution of transactions at different isolation levels. IEEE Trans. Knowl. Data Eng. 16(9), 1070–1081 (2004) · doi:10.1109/TKDE.2004.34 |
| [24] | Napper, J., Alvisi, L.: Lock-free serializable transactions. Technical Report TR-05-04, The University of Texas at Austin (2005) |
| [25] | Papadimitriou, C.H.: The serializability of concurrent database updates. J. Assoc. Comput. Mach. 26(4), 631–653 (1979) · Zbl 0419.68036 · doi:10.1145/322154.322158 |
| [26] | 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) · Zbl 1155.68341 |
| [27] | Riegel, T., Fetzer, C., Felber, P.: Snapshot isolation for software transactional memory. In: 1st ACM SIGPLAN Workshop on Transactional Computing (2006) · Zbl 1188.68101 |
| [28] | 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) · Zbl 1283.68120 |
| [29] | Weikum, G., Vossen, G.: Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery. Morgan Kaufmann, San Mateo (2001) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
