poster

Wait-free linked-lists

Authors:

Shahar Timnat,

Anastasia Braginsky,

Alex Kogan,

Erez PetrankAuthors Info & Claims

ACM SIGPLAN Notices, Volume 47, Issue 8

Pages 309 - 310

https://doi.org/10.1145/2370036.2145869

Published: 25 February 2012 Publication History

Get Access

Abstract

The linked-list data structure is fundamental and ubiquitous. Lock-free versions of the linked-list are well known. However, the existence of a practical wait-free linked-list has been open. In this work we designed such a linked-list. To achieve better performance, we have also extended this design using the fast-path-slow-path methodology. The resulting implementation achieves performance which is competitive with that of Harris's lock-free list, while still guaranteeing non-starvation via wait-freedom. We have also developed a proof for the correctness and the wait-freedom of our design.

References

[1]

Panagiota Fatourou and Nikolaos D. Kallimanis. A highly-efficient wait-free universal construction. In SPAA, pages 325--334, 2011.

Digital Library

Google Scholar

[2]

Mikhail Fomitchev and Eric Ruppert. Lock-free linked lists and skip lists. In Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, PODC '04, pages 50--59, New York, NY, USA, 2004. ACM.

Digital Library

Google Scholar

[3]

Timothy L. Harris. A pragmatic implementation of non-blocking linked-lists. In Proceedings of the 15th International Conference on Distributed Computing, DISC '01, London, UK, UK, 2001. Springer-Verlag.

Digital Library

Google Scholar

[4]

Maurice Herlihy. A methodology for implementing highly concurrent objects. ACM Trans. Program. Lang. Syst., 15(5):745--770, 1993.

Digital Library

Google Scholar

[5]

Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2008.

Digital Library

Google Scholar

[6]

Alex Kogan and Erez Petrank. Wait-free queues with multiple enqueuers and dequeuers. In PPOPP, pages 223--234, 2011.

Digital Library

Google Scholar

[7]

Alex Kogan and Erez Petrank. A methodology for creating fast wait-free data structures. In PPOPP, 2012.

Digital Library

Google Scholar

[8]

Maged M. Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, SPAA '02, pages 73--82, New York, NY, USA, 2002. ACM.

Digital Library

Google Scholar

[9]

John D. Valois. Lock-free linked lists using compare-and-swap. In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, PODC '95, pages 214--222, New York, NY, USA, 1995. ACM.

Digital Library

Google Scholar

Cited By

View all

Feldman SLaBorde PDechev D(2015)Tervel: A unification of descriptor-based techniques for non-blocking programming2015 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS)10.1109/SAMOS.2015.7363668(131-140)Online publication date: Jul-2015
https://doi.org/10.1109/SAMOS.2015.7363668
Feldman SLaborde PDechev D(2015)A Wait-Free Multi-Word Compare-and-Swap OperationInternational Journal of Parallel Programming10.1007/s10766-014-0308-743:4(572-596)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1007/s10766-014-0308-7
Petrank ETimnat S(2013)Lock-Free Data-Structure IteratorsProceedings of the 27th International Symposium on Distributed Computing - Volume 820510.1007/978-3-642-41527-2_16(224-238)Online publication date: 14-Oct-2013
https://dl.acm.org/doi/10.1007/978-3-642-41527-2_16
Show More Cited By

Index Terms

Wait-free linked-lists
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Parallel programming languages

Recommendations

Wait-free linked-lists
PPoPP '12: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming

The linked-list data structure is fundamental and ubiquitous. Lock-free versions of the linked-list are well known. However, the existence of a practical wait-free linked-list has been open. In this work we designed such a linked-list. To achieve better ...
Lock-Free Data-Structure Iterators
DISC 2013: Proceedings of the 27th International Symposium on Distributed Computing - Volume 8205

Concurrent data structures are often used with large concurrent software. An iterator that traverses the data structure items is a highly desirable interface that often exists for sequential data structures but is missing from almost all concurrent data-...
A practical wait-free simulation for lock-free data structures
PPoPP '14: Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming

Lock-free data structures guarantee overall system progress, whereas wait-free data structures guarantee the progress of each and every thread, providing the desirable non-starvation guarantee for concurrent data structures. While practical lock-free ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGPLAN Notices Volume 47, Issue 8

PPOPP '12

August 2012

334 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2370036

Issue’s Table of Contents

PPoPP '12: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming
February 2012
352 pages
ISBN:9781450311601
DOI:10.1145/2145816
General Chair:
J. Ramanujam
Louisiana State University, USA
,
Program Chair:
P. Sadayappan
The Ohio State University, USA

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 February 2012

Published in SIGPLAN Volume 47, Issue 8

Check for updates

Author Tags

Qualifiers

Poster

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
678
Total Downloads

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

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Feldman SLaBorde PDechev D(2015)Tervel: A unification of descriptor-based techniques for non-blocking programming2015 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS)10.1109/SAMOS.2015.7363668(131-140)Online publication date: Jul-2015
https://doi.org/10.1109/SAMOS.2015.7363668
Feldman SLaborde PDechev D(2015)A Wait-Free Multi-Word Compare-and-Swap OperationInternational Journal of Parallel Programming10.1007/s10766-014-0308-743:4(572-596)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1007/s10766-014-0308-7
Petrank ETimnat S(2013)Lock-Free Data-Structure IteratorsProceedings of the 27th International Symposium on Distributed Computing - Volume 820510.1007/978-3-642-41527-2_16(224-238)Online publication date: 14-Oct-2013
https://dl.acm.org/doi/10.1007/978-3-642-41527-2_16
Timnat SBraginsky AKogan APetrank E(2012)Wait-Free Linked-ListsPrinciples of Distributed Systems10.1007/978-3-642-35476-2_23(330-344)Online publication date: 2012
https://doi.org/10.1007/978-3-642-35476-2_23
Wang JLiu DFu XXiao FTian C(2022)DHash: Dynamic Hash Tables With Non-Blocking Regular OperationsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.315149933:12(3274-3290)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TPDS.2022.3151499
Correia ARamalhete PFelber PLee JPetrank E(2021)OrcGCProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441596(205-218)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3437801.3441596
Peri SReddy CSa M(2019)An Efficient Practical Concurrent Wait-Free Unbounded Graph2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS)10.1109/HPCC/SmartCity/DSS.2019.00348(2487-2494)Online publication date: Aug-2019
https://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00348
Cohen N(2018)Every data structure deserves lock-free memory reclamationProceedings of the ACM on Programming Languages10.1145/32765132:OOPSLA(1-24)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276513
Peng YHao Z(2018)FA-Stack: A Fast Array-Based Stack with Wait-Free Progress GuaranteeIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.277012129:4(843-857)Online publication date: 1-Apr-2018
https://doi.org/10.1109/TPDS.2017.2770121
Sheffi GGolan-Gueta GPetrank E(2018)A Scalable Linearizable Multi-Index Table2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2018.00029(200-211)Online publication date: Jul-2018
https://doi.org/10.1109/ICDCS.2018.00029
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.

Cited By

Index Terms

Recommendations

Wait-free linked-lists

Lock-Free Data-Structure Iterators

A practical wait-free simulation for lock-free data structures