invited-talk

Concurrent Data Structures

Authors:

Trevor BrownAuthors Info & Claims

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

Pages 151 - 153

https://doi.org/10.1145/2933057.2933123

Published: 25 July 2016 Publication History

Abstract

Data structures are an important component of efficient and well-structured programs. In shared memory distributed computing, correct data structures are difficult to construct because concurrent accesses by different processes can conflict with one another. One simple approach is to use a global lock to restrict access to one process at a time. But this can severely affect performance. This talk will present a survey of some of the interesting techniques that have been developed to build efficient concurrent data structures. It will also discuss how we think concurrent data structures should be evaluated.

References

[1]

Y. Afek, M. Hakimi, and A. Morrison. Fast and scalable rendezvousing. Distributed Computing, 26(4):243--269, 2013.

Digital Library

[2]

R. Bayer and M. Schkolnick. Concurrency of operations on B-trees. Acta Inf., 9:1--21, 1977.

Digital Library

[3]

J. Boyar, R. Fagerberg, and K. S. Larsen. Amortization results for chromatic search trees, with an application to priority queues. Journal of Computer and System Sciences, 55(3):504--521, 1997.

Digital Library

[4]

N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun. A practical concurrent binary search tree. In Proc. 15th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 257--268, 2010.

Digital Library

[5]

T. Brown. Brief announcement: Faster data structures in transactional memory using three paths. In Proc. 29th International Symposium on Distributed Computing (DISC), pages 671--672, 2015.

[6]

T. Brown. Reclaiming memory for lock-free data structures: There has to be a better way. In Proc. 34rd ACM Symposium on Principles of Distributed Computing (PODC), pages 261--270, 2015.

Digital Library

[7]

T. Brown, F. Ellen, and E. Ruppert. Pragmatic primitives for non-blocking data structures. In Proc. 32nd ACM Symposium on Principles of Distributed Computing (PODC), pages 13--22, 2013.

Digital Library

[8]

T. Brown, F. Ellen, and E. Ruppert. A general technique for non-blocking trees. In Proc. 19th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 329--342, 2014.

Digital Library

[9]

F. Ellen, P. Fatourou, J. Helga, and E. Ruppert. The amortized complexity of non-blocking binary search trees. In Proc. 33rd ACM Symposium on Principles of Distributed Computing (PODC), pages 332--340, 2014.

Digital Library

[10]

F. Ellen, P. Fatourou, E. Ruppert, and F. van Breugel. Non-blocking binary search trees. In Proc. 29th ACM Symposium on Principles of Distributed Computing (PODC), pages 131--140, 2010.

Digital Library

[11]

F. E. Fich, V. Luchangco, M. Moir, and N. Shavit. Obstruction-free algorithms can be practically wait-free. In Proc. 19th International Conference on Distributed Computing (DISC), pages 78--92, 2005.

Digital Library

[12]

M. Fomitchev and E. Ruppert. Lock-free linked lists and skip lists. In Proc. 23rd ACM Symposium on Principles of Distributed Computing (PODC), pages 50--59, 2004.

Digital Library

[13]

G. Giakkoupis, M. Helmi, L. Higham, and P. Woelfel. An O(√n) space bound for obstruction-free leader election. In Proc. 27th International Symposium on Distributed Computing (DISC), pages 46--60, 2013.

Digital Library

[14]

T. L. Harris. A pragmatic implementation of non-blocking linked-lists. In Proc. 15th International Conference on Distributed Computing (DISC), pages 300--314, 2001.

Digital Library

[15]

M. Herlihy, V. Luchangco, P. A. Martin, and M. Moir. Nonblocking memory management support for dynamic-sized data structures. ACM Trans. Comput. Syst., 23(2):146--196, 2005.

Digital Library

[16]

M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2012.

Digital Library

[17]

U. Manber. On maintaining dynamic information in a concurrent environment (preliminary version). In Proc. 16th Annual ACM Symposium on Theory of Computing (STOC), pages 273--278, 1984.

Digital Library

[18]

M. Michael. Hazard pointers: Safe memory reclamation for lock-free objects. IEEE Transactions on Parallel and Distributed Systems, 15(6):491--504, 2004.

Digital Library

[19]

M. Moir and N. Shavit. Concurrent data structures. In Handbook of Data Structures and Applications. Chapman and Hall/CRC Press, 2004.

[20]

E. Petrank and S. Timnat. Lock-free data-structure iterators. In Proc. 27th International Symposium on Distributed Computing (DISC), pages 224--238, 2013.

Digital Library

[21]

A. Prokopec, N. Bronson, P. Bagwell, and M. Odersky. Concurrent tries with efficient non-blocking snapshots. In Proc. 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 151--160, 2012.

Digital Library

[22]

N. Shavit and G. Taubenfeld. The computability of relaxed data structures: Queues and stacks as examples. In Proc. 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 414--428, 2015.

Digital Library

[23]

N. Shavit and D. Touitou. Elimination trees and the construction of pools and stacks. Theory Comput. Syst., 30(6):645--670, 1997.

Digital Library

[24]

S. Timnat and E. Petrank. A practical wait-free simulation for lock-free data structures. In Proc. ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 357--368, 2014.

Digital Library

[25]

J. D. Valois. Lock-free linked lists using compare-and-swap. In Proc. 14th ACM Symposium on Principles of Distributed Computing (PODC), pages 214--222, 1995.

Digital Library

Cited By

Diep THa PFürlinger K(2022)A general approach for supporting nonblocking data structures on distributed-memory systemsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.11.006Online publication date: Nov-2022
https://doi.org/10.1016/j.jpdc.2022.11.006
Diep TFurlinger K(2021)Nonblocking Data Structures for Distributed-Memory Machines: Stacks as an Example2021 29th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)10.1109/PDP52278.2021.00012(9-17)Online publication date: Mar-2021
https://doi.org/10.1109/PDP52278.2021.00012

Index Terms

Concurrent Data Structures
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
    2. Distributed algorithms
  2. Models of computation
    1. Concurrency
      1. Distributed computing models

Recommendations

Adaptive lock-free data structures in Haskell: a general method for concurrent implementation swapping
Haskell 2017: Proceedings of the 10th ACM SIGPLAN International Symposium on Haskell

A key part of implementing high-level languages is providing built- in and default data structures. Yet selecting good defaults is hard. A mutable data structure’s workload is not known in advance, and it may shift over its lifetime—e.g., between read-...
Adaptive lock-free data structures in Haskell: a general method for concurrent implementation swapping
Haskell '17

A key part of implementing high-level languages is providing built- in and default data structures. Yet selecting good defaults is hard. A mutable data structure’s workload is not known in advance, and it may shift over its lifetime—e.g., between read-...
A methodology for creating fast wait-free data structures
PPoPP '12: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming

Lock-freedom is a progress guarantee that ensures overall program progress. Wait-freedom is a stronger progress guarantee that ensures the progress of each thread in the program. While many practical lock-free algorithms exist, wait-free algorithms are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

July 2016

508 pages

ISBN:9781450339643

DOI:10.1145/2933057

General Chair:
George Giakkoupis
INRIA, France

Copyright © 2016 Owner/Author.

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2016

Check for updates

Author Tags

Qualifiers

Invited-talk

Funding Sources

Natural Sciences and Engineering Research Council of Canada

Conference

PODC '16

Sponsor:

PODC '16: ACM Symposium on Principles of Distributed Computing

July 25 - 28, 2016

Illinois, Chicago, USA

Acceptance Rates

PODC '16 Paper Acceptance Rate 40 of 149 submissions, 27%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
517
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Diep THa PFürlinger K(2022)A general approach for supporting nonblocking data structures on distributed-memory systemsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.11.006Online publication date: Nov-2022
https://doi.org/10.1016/j.jpdc.2022.11.006
Diep TFurlinger K(2021)Nonblocking Data Structures for Distributed-Memory Machines: Stacks as an Example2021 29th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)10.1109/PDP52278.2021.00012(9-17)Online publication date: Mar-2021
https://doi.org/10.1109/PDP52278.2021.00012

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