More Web Proxy on the site http://driver.im/

research-article

On the liveness of transactional memory

Authors:

Victor Bushkov,

Rachid Guerraoui,

Michał KapałkaAuthors Info & Claims

PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computing

Pages 9 - 18

https://doi.org/10.1145/2332432.2332435

Published: 16 July 2012 Publication History

Abstract

Despite the large amount of work on Transactional Memory (TM), little is known about how much liveness it could provide. This paper presents the first formal treatment of the question. We prove that no TM implementation can ensure local progress, the analogous of wait-freedom in the TM context, and we highlight different ways to circumvent the impossibility.

References

[1]

M. Abadi, A. Birrell, T. Harris, and M. Isard. Semantics of transactional memory and automatic mutual exclusion. ACM Trans. Program. Lang. Syst., 33(1):2:1--2:50, jan 2011.

Digital Library

[2]

B. Alpern and F. B. Schneider. Defining liveness. Inf. Process. Lett., 21(4):181--185, 1985.

[3]

D. Dice, O. Shalev, and N. Shavit. Transactional locking ii. In Proceedings of DISC'06, pages 194--208. Springer-Verlag, 2006.

Digital Library

[4]

S. Doherty, L. Groves, V. Luchangco, and M. Moir. Towards formally specifying and verifying transactional memory. Electron. Notes Theor. Comput. Sci., 259:245--261, dec 2009.

Digital Library

[5]

A. Dragojević, R. Guerraoui, and M. Kapalka. Stretching transactional memory. In Proceedings of ACM PLDI'09, pages 155--165. ACM, 2009.

Digital Library

[6]

P. Felber, C. Fetzer, and T. Riegel. Dynamic performance tuning of word-based software transactional memory. In Proceedings of ACM PPoPP'08, pages 237--246. ACM, 2008.

Digital Library

[7]

K. Fraser. Practical Lock-Freedom. PhD thesis, University of Cambridge, 2003.

[8]

R. Gawlick, R. Segala, J. F. Søgaard-Andersen, and N. A. Lynch. Liveness in timed and untimed systems. Information and Computation, 141(2):119--171, mar 1998.

Digital Library

[9]

R. Guerraoui and M. Kapalka. Principles of Transactional Memory. Morgan and Claypool, 2010.

[10]

T. Harris, J. R. Larus, and R. Rajwar. Transactional Memory, 2nd edition. Morgan and Claypool, 2010.

Digital Library

[11]

M. Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124--149, jan 1991.

Digital Library

[12]

M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer, III. Software transactional memory for dynamic-sized data structures. In Proceedings of ACM PODC'03, pages 92--101. ACM, 2003.

Digital Library

[13]

M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. SIGARCH Comput. Archit. News, 21(2):289--300, may 1993.

Digital Library

[14]

M. Herlihy and N. Shavit. On the nature of progress. In Proceedings of the 15th international conference on Principles of Distributed Systems, pages 313--328. Springer-Verlag, 2011.

Digital Library

[15]

D. Imbs, J. R. de Mendivil, and M. Raynal. Brief announcement: virtual world consistency: a new condition for STM systems. In Proceedings of ACM PODC'09, pages 280--281. ACM, 2009.

Digital Library

[16]

S. Jagannathan, J. Vitek, A. Welc, and A. Hosking. A transactional object calculus. Sci. Comput. Program., 57(2):164--186, aug 2005.

Digital Library

[17]

V. Menon, S. Balensiefer, T. Shpeisman, A.-R. Adl-Tabatabai, R. L. Hudson, B. Saha, and A. Welc. Practical weak-atomicity semantics for java stm. In Proceedings of ACM SPAA'08, pages 314--325. ACM, 2008.

Digital Library

[18]

K. F. Moore and D. Grossman. High-level small-step operational semantics for transactions. In Proceedings of ACM POPL'08, pages 51--62. ACM, 2008.

Digital Library

[19]

C. H. Papadimitriou. The serializability of concurrent database updates. J. ACM, 26(4):631--653, oct 1979.

Digital Library

[20]

N. Shavit and D. Touitou. Software transactional memory. In Proceedings of ACM PODC'95, pages 204--213, New York, NY, USA, 1995. ACM.

Digital Library

[21]

J.-T. Wamhoff and C. Fetzer. The universal transactional memory construction. In Proceedings of TRANSACT'11, 2011.

Cited By

Chaudhary VJuyal CKulkarni SKumari SPeri S(2022)Achieving starvation-freedom in multi-version transactional memory systemsComputing10.1007/s00607-021-00994-y104:10(2159-2179)Online publication date: 10-Jan-2022
https://doi.org/10.1007/s00607-021-00994-y
Attiya HFatourou PHans SKanellou E(2021)Staleness and Local Progress in Transactional MemoryNetworked Systems10.1007/978-3-030-67087-0_15(227-243)Online publication date: 14-Jan-2021
https://doi.org/10.1007/978-3-030-67087-0_15
Juyal CKulkarni SKumari SPeri SSomani A(2019)Achieving Starvation-Freedom with Greater Concurrency in Multi-Version Object-based Transactional Memory SystemsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-34992-9_17(209-227)Online publication date: 14-Nov-2019
https://doi.org/10.1007/978-3-030-34992-9_17
Show More Cited By

Index Terms

On the liveness of transactional memory
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software creation and management
    1. Designing software
      1. Requirements analysis
  2. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages

Recommendations

WFR-TM

Transactional Memory (TM) is a promising concurrent programming paradigm which employs transactions to achieve synchronization in accessing common data known as transactional variables. A transaction may either commit, making its updates to ...
Relaxed Concurrency Control in Software Transactional Memory

Some of today's TM systems implement the two-phase-locking (2PL) algorithm which aborts transactions every time a conflict occurs. 2PL is a simple algorithm that provides fast transactional operations. However, it limits concurrency in benchmarks with ...
Extensible software transactional memory
C3S2E '10: Proceedings of the Third C* Conference on Computer Science and Software Engineering

XSTM is a software transactional memory that can be extended by pluggable components. Extensions can access transactions read and write sets through an API, and process them e.g., for logging, change notification, state persistence or replication. This ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computing

July 2012

410 pages

ISBN:9781450314503

DOI:10.1145/2332432

General Chair:
Darek Kowalski
U. of Liverpool, UK and IMDEA Networks, Spain
,
Program Chair:
Alessandro Panconesi
Sapienza, University of Rome, Italy

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
INESC-ID: INESC-ID Lisboa

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '12

Sponsor:

SIGOPS
SIGACT
INESC-ID

PODC '12: ACM Symposium on Principles of Distributed Computing

July 16 - 18, 2012

Madeira, Portugal

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
307
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chaudhary VJuyal CKulkarni SKumari SPeri S(2022)Achieving starvation-freedom in multi-version transactional memory systemsComputing10.1007/s00607-021-00994-y104:10(2159-2179)Online publication date: 10-Jan-2022
https://doi.org/10.1007/s00607-021-00994-y
Attiya HFatourou PHans SKanellou E(2021)Staleness and Local Progress in Transactional MemoryNetworked Systems10.1007/978-3-030-67087-0_15(227-243)Online publication date: 14-Jan-2021
https://doi.org/10.1007/978-3-030-67087-0_15
Juyal CKulkarni SKumari SPeri SSomani A(2019)Achieving Starvation-Freedom with Greater Concurrency in Multi-Version Object-based Transactional Memory SystemsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-34992-9_17(209-227)Online publication date: 14-Nov-2019
https://doi.org/10.1007/978-3-030-34992-9_17
Chaudhary VJuyal CKulkarni SKumari SPeri S(2019)Achieving Starvation-Freedom in Multi-version Transactional Memory SystemsNetworked Systems10.1007/978-3-030-31277-0_20(291-310)Online publication date: 14-Sep-2019
https://doi.org/10.1007/978-3-030-31277-0_20
Bushkov VDziuma DFatourou PGuerraoui R(2018)The PCL TheoremJournal of the ACM10.1145/326614166:1(1-66)Online publication date: 12-Dec-2018
https://dl.acm.org/doi/10.1145/3266141
Fatourou PKanellou EKosmas ERabbi M(2016)WFR-TMJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.05.00296:C(134-151)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2016.05.002
Ellen FFatourou PKosmas EMilani ATravers C(2016)Universal constructions that ensure disjoint-access parallelism and wait-freedomDistributed Computing10.1007/s00446-015-0261-829:4(251-277)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s00446-015-0261-8
Koskinen EParkinson M(2015)The Push/Pull model of transactionsACM SIGPLAN Notices10.1145/2813885.273799550:6(186-195)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2813885.2737995
Peluso SPalmieri RRomano PRavindran BQuaglia FGeorgiou CSpirakis P(2015)Disjoint-Access ParallelismProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767438(217-226)Online publication date: 21-Jul-2015
https://dl.acm.org/doi/10.1145/2767386.2767438
Bushkov VGuerraoui RGeorgiou CSpirakis P(2015)Safety-Liveness Exclusion in Distributed ComputingProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767401(227-236)Online publication date: 21-Jul-2015
https://dl.acm.org/doi/10.1145/2767386.2767401
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents