Abstract
Transactional memory allows the user to declare sequences of instructions as speculative transactions that can either commit or abort, providing all-or-nothing semantics. If a transaction commits, it should appear to execute sequentially, so that the committed transactions constitute a correct sequential execution. If a transaction aborts, none of its instructions should affect other transactions. These semantics allow the programmer to incorporate sequential code within transactions and let the transactional memory care about conflicts between concurrent transactions. In this sense, it is important that the memory is safe, i.e., every transaction has a consistent view even if the transaction aborts later. Otherwise, inconsistencies not predicted by the sequential program may cause a fatal irrecoverable error or an infinite loop. Furthermore, in a general setting, where a transaction may be explicitly aborted by the user or an external contention manager, a transaction should not be allowed to read from a not yet committed transaction, which is often called deferred-update semantics. This chapter overviews the scope of consistency criteria proposed so far to capture deferred-update semantics, and shows that—under reasonable conditions—the semantics induces a safety property.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alpern, B., Schneider, F.B.: Defining liveness. Information Processing Letters 21(4), 181–185 (1985)
Attiya, H., Gotsman, A., Hans, S., Rinetzky, N.: Safety of live transactions in transactional memory: TMS is necessary and sufficient. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 376–390. Springer, Heidelberg (2014)
Attiya, H., Hans, S., Kuznetsov, P., Ravi, S.: Safety of deferred update in transactional memory. In: ICDCS, pp. 601–610 (2013)
Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations, and Advanced Topics, 2nd edn. Wiley Interscience (2004)
Doherty, S., Groves, L., Luchangco, V., Moir, M.: Towards formally specifying and verifying transactional memory. Formal Asp. Comput. 25(5), 769–799 (2013)
Guerraoui, R., Henzinger, T.A., Singh, V.: Permissiveness in transactional memories. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol. 5218, pp. 305–319. Springer, Heidelberg (2008)
Guerraoui, R., Kapalka, M.: Principles of Transactional Memory, Synthesis Lectures on Distributed Computing Theory. Morgan and Claypool (2010)
Guerraoui, R., Ruppert, E.: Linearizability is not always a safety property. In: Noubir, G., Raynal, M. (eds.) NETYS 2014. LNCS, vol. 8539, pp. 57–69. Springer, Heidelberg (2014)
Hadzilacos, V.: A theory of reliability in database systems. J. ACM 35(1), 121–145 (1988)
Herlihy, M., Moss, J.E.B.: Transactional memory: Architectural support for lock-free data structures. SIGARCH Comput. Archit. News 21(2), 289–300 (1993)
Herlihy, M., Wing, J.M.: Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)
Imbs, D., Raynal, M.: Virtual world consistency: A condition for STM systems (with a versatile protocol with invisible read operations). Theor. Comput. Sci. 444 (July 2012)
König, D.: Theorie der Endlichen und Unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe. Akad. Verlag (1936)
Kuznetsov, P., Ravi, S.: On the cost of concurrency in transactional memory. CoRR, abs/1103.1302 (2011)
Lesani, M., Luchangco, V., Moir, M.: Putting opacity in its place. In: WTTM (2012)
Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann (1996)
Owicki, S.S., Lamport, L.: Proving liveness properties of concurrent programs. ACM Trans. Program. Lang. Syst. 4(3), 455–495 (1982)
Papadimitriou, C.H.: The serializability of concurrent database updates. J. ACM 26, 631–653 (1979)
Shavit, N., Touitou, D.: Software transactional memory. In: PODC 1995, pp. 204–213 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Attiya, H., Hans, S., Kuznetsov, P., Ravi, S. (2015). Safety and Deferred Update in Transactional Memory. In: Guerraoui, R., Romano, P. (eds) Transactional Memory. Foundations, Algorithms, Tools, and Applications. Lecture Notes in Computer Science, vol 8913. Springer, Cham. https://doi.org/10.1007/978-3-319-14720-8_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-14720-8_3
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-14719-2
Online ISBN: 978-3-319-14720-8
eBook Packages: Computer ScienceComputer Science (R0)