Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Transactions in the Jungle
 
conference paper

Transactions in the Jungle

Guerraoui, Rachid  
•
Henzinger, Thomas  
•
Kapalka, Michal
Show more
2010
Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures
22nd ACM Symposium on Parallelism in Algorithms and Architectures

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.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1145/1810479.1810529
Web of Science ID

WOS:000281485500037

Author(s)
Guerraoui, Rachid  
Henzinger, Thomas  
Kapalka, Michal
Singh, Vasu
Date Issued

2010

Publisher

Acm Order Department

Publisher place

Baltimore, Md 21264 Usa

Published in
Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures
Start page

263

End page

272

Subjects

Transactional memory

•

memory models

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
MTC  
DCL  
Event nameEvent placeEvent date
22nd ACM Symposium on Parallelism in Algorithms and Architectures

Thira, Santorini, Greece

June 13–15, 2010

Available on Infoscience
June 1, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/50545
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés