Transactions in the jungle

Guerraoui R, Henzinger TA, Kapalka M, Singh V. 2010. Transactions in the jungle. SPAA: ACM Symposium on Parallel Algorithms and Architectures, 263–272.

Download
OA IST-2012-46-v1+1_Transactions_in_the_jungle.pdf 246.41 KB [Submitted Version]

Conference Paper | Published | English
Author
Guerraoui, Rachid; Henzinger, Thomas AISTA ; Kapalka, Michal; Singh, VasuISTA
Abstract
Transactional memory (TM) has shown potential to simplify the task of writing concurrent programs. Inspired by classical work on databases, formal definitions of the semantics of TM executions have been proposed. Many of these definitions assumed that accesses to shared data are solely performed through transactions. In practice, due to legacy code and concurrency libraries, transactions in a TM have to share data with non-transactional operations. The semantics of such interaction, while widely discussed by practitioners, lacks a clear formal specification. Those interactions can vary, sometimes in subtle ways, between TM implementations and underlying memory models. We propose a correctness condition for TMs, parametrized opacity, to formally capture the now folklore notion of strong atomicity by stipulating the two following intuitive requirements: first, every transaction appears as if it is executed instantaneously with respect to other transactions and non-transactional operations, and second, non-transactional operations conform to the given underlying memory model. We investigate the inherent cost of implementing parametrized opacity. We first prove that parametrized opacity requires either instrumenting non-transactional operations (for most memory models) or writing to memory by transactions using potentially expensive read-modify-write instructions (such as compare-and-swap). Then, we show that for a class of practical relaxed memory models, parametrized opacity can indeed be implemented with constant-time instrumentation of non-transactional writes and no instrumentation of non-transactional reads. We show that, in practice, parametrizing the notion of correctness allows developing more efficient TM implementations.
Publishing Year
Date Published
2010-06-13
Page
263 - 272
Conference
SPAA: ACM Symposium on Parallel Algorithms and Architectures
Conference Location
Santorini, Greece
Conference Date
2010-06-13 – 2010-06-15
IST-REx-ID

Cite this

Guerraoui R, Henzinger TA, Kapalka M, Singh V. Transactions in the jungle. In: ACM; 2010:263-272. doi:10.1145/1810479.1810529
Guerraoui, R., Henzinger, T. A., Kapalka, M., & Singh, V. (2010). Transactions in the jungle (pp. 263–272). Presented at the SPAA: ACM Symposium on Parallel Algorithms and Architectures, Santorini, Greece: ACM. https://doi.org/10.1145/1810479.1810529
Guerraoui, Rachid, Thomas A Henzinger, Michal Kapalka, and Vasu Singh. “Transactions in the Jungle,” 263–72. ACM, 2010. https://doi.org/10.1145/1810479.1810529.
R. Guerraoui, T. A. Henzinger, M. Kapalka, and V. Singh, “Transactions in the jungle,” presented at the SPAA: ACM Symposium on Parallel Algorithms and Architectures, Santorini, Greece, 2010, pp. 263–272.
Guerraoui R, Henzinger TA, Kapalka M, Singh V. 2010. Transactions in the jungle. SPAA: ACM Symposium on Parallel Algorithms and Architectures, 263–272.
Guerraoui, Rachid, et al. Transactions in the Jungle. ACM, 2010, pp. 263–72, doi:10.1145/1810479.1810529.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
f2ad6c00a6304da34bf21bcdcfd36c4b


Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar