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

Article

Scalable and lock-free concurrent dictionaries

Authors:

Håkan Sundell,

Philippas TsigasAuthors Info & Claims

SAC '04: Proceedings of the 2004 ACM symposium on Applied computing

Pages 1438 - 1445

https://doi.org/10.1145/967900.968188

Published: 14 March 2004 Publication History

Abstract

We present an efficient and practical lock-free implementation of a concurrent dictionary that is suitable for both fully concurrent (large multi-processor) systems as well as pre-emptive (multi-process) systems. Many algorithms for concurrent dictionaries are based on mutual exclusion. However, mutual exclusion causes blocking which has several drawbacks and degrades the system's overall performance. Non-blocking algorithms avoid blocking, and are either lockfree or wait-free. Our algorithm is based on the randomized sequential list structure called Skiplist, and implements the full set of operations on a dictionary that is suitable for practical settings. In our performance evaluation we compare our algorithm with the most efficient non-blocking implementation of dictionaries known. The experimental results clearly show that our algorithm outperforms the other lockfree algorithm for dictionaries with realistic sizes, both on fully concurrent as well as pre-emptive systems.

References

[1]

J. Aspnes and M. Herlihy. Wait-free data structures in the asynchronous PRAM model. In ACM Symposium on Parallel Algorithms and Architectures, pages 340--349, 2000.

Digital Library

[2]

L. Boug, J. Gabarr, and X. Messeguer. Concurrent AVL revisited: Self-balancing distributed search trees. Research Report RR95--45, LIP, ENS Lyon, 1995.

[3]

T. L. Harris. A pragmatic implementation of non-blocking linked lists. In Proceedings of the 15th International Symposium of Distributed Computing, pages 300-314, Oct. 2001.

Digital Library

[4]

M. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 11(1):124--149, Jan. 1991.

Digital Library

[5]

M. Herlihy and J. Wing. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463--492, 1990.

Digital Library

[6]

M. M. Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the 14th ACM Symposium on Parallel Algorithms and Architectures, pages 73--82, 2002.

Digital Library

[7]

M. M. Michael. Safe memory reclamation for dynamic lock-free objects using atomic reads and writes. In Proceedings of the 21st ACM Symposium on Principles of Distributed Computing, pages 21--30, 2002.

Digital Library

[8]

M. M. Michael and M. L. Scott. Correction of a memory management method for lock-free data structures. Technical report, Computer Science Department, University of Rochester, 1995.

Digital Library

[9]

W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33(6):668--676, 1990.

Digital Library

[10]

R. Rajkumar. Real-time synchronization protocols for shared memory multiprocessors. In Proceedings of the 10th International Conference on Distributed Computing Systems, pages 116--123, 1990.

[11]

L. Sha, R. Rajkumar, and J. Lehoczky. Priority inheritance protocols: An approach to real-time synchronization. IEEE Transactions on Computers, 39(9):1175--1185, Sept. 1990.

Digital Library

[12]

A. Silberschatz and P. Galvin. Operating System Concepts. Addison Wesley, 1994.

Digital Library

[13]

H. Sundell and P. Tsigas. NOBLE: A non-blocking inter-process communication library. In Proceedings of the 6th Workshop on Languages, Compilers and Run-time Systems for Scalable Computers, Lecture Notes in Computer Science. Springer Verlag, 2002.

[14]

H. Sundell and P. Tsigas. Fast and lock-free concurrent priority queues for multi-thread systems. In Proceedings of the 17th International Parallel and Distributed Processing Symposium. IEEE press, 2003.

Digital Library

[15]

H. Sundell and P. Tsigas. Scalable and lock-free concurrent dictionaries, extended version. Technical report, Computing Science, Chalmers University of Technology, Dec. 2003.

[16]

P. Tsigas and Y. Zhang. Integrating non-blocking synchronisation in parallel applications: Performance advantages and methodologies. In Proceedings of the 3rd ACM Workshop on Software and Performance, pages 55--67, ACM Press, 2002.

Digital Library

[17]

J. D. Valois. Lock-Free Data Structures. PhD thesis, Rensselaer Polytechnic Institute, Troy, New York, 1995.

Digital Library

Cited By

Kobus TKokociński MWojciechowski PLee JAgrawal KSpear M(2022)JiffyProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508437(400-415)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508437
Ouyang XZhu Y(2022)Core-aware combiningJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.01.001162:C(27-43)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1016/j.jpdc.2022.01.001
Ruiz ARivas MHarbour M(2020)Non-Blocking Synchronization Between Real-Time and Non-Real-Time ApplicationsIEEE Access10.1109/ACCESS.2020.30153858(147618-147634)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3015385
Show More Cited By

Index Terms

Scalable and lock-free concurrent dictionaries

Recommendations

Fast and lock-free concurrent priority queues for multi-thread systems

We present an efficient and practical lock-free implementation of a concurrent priority queue that is suitable for both fully concurrent (large multi-processor) systems as well as pre-emptive (multi-process) systems. Many algorithms for concurrent ...
Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems
IPDPS '03: Proceedings of the 17th International Symposium on Parallel and Distributed Processing

We present an efficient and practical lock-free implementation of a concurrent priority queue that is suitable for both fully concurrent (large multi-processor) systems as well as pre-emptive (multi-process) systems. Many algorithms for concurrent ...
Lock-free deques and doubly linked lists

We present a practical lock-free shared data structure that efficiently implements the operations of a concurrent deque as well as a general doubly linked list. The implementation supports parallelism for disjoint accesses and uses atomic primitives ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '04: Proceedings of the 2004 ACM symposium on Applied computing

March 2004

1733 pages

ISBN:1581138121

DOI:10.1145/967900

Conference Chair:
Hisham M. Haddad
Kennesaw State University
,
Program Chairs:
Andrea Omicini
Università degli Studi di Bologna a Cesena
,
Roger L. Wainwright
University of Tulsa
,
Publications Chair:
Lorie M. Liebrock
New Mexico Institute of Mining and Technology

Copyright © 2004 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

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 March 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SAC04

Sponsor:

SIGAPP

SAC04: The 2004 ACM Symposium on Applied Computing

March 14 - 17, 2004

Nicosia, Cyprus

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
579
Total Downloads

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

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kobus TKokociński MWojciechowski PLee JAgrawal KSpear M(2022)JiffyProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508437(400-415)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508437
Ouyang XZhu Y(2022)Core-aware combiningJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.01.001162:C(27-43)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1016/j.jpdc.2022.01.001
Ruiz ARivas MHarbour M(2020)Non-Blocking Synchronization Between Real-Time and Non-Real-Time ApplicationsIEEE Access10.1109/ACCESS.2020.30153858(147618-147634)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3015385
Ma WZhu YLi CGuo MBao Y(2019)BiloKey : A Scalable Bi-Index Locality-Aware In-Memory Key-Value StoreIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.289159930:7(1528-1540)Online publication date: 1-Jul-2019
https://doi.org/10.1109/TPDS.2019.2891599
Shafiei N(2019)Non-blocking Patricia tries with replace operationsDistributed Computing10.1007/s00446-019-00347-1Online publication date: 4-Feb-2019
https://doi.org/10.1007/s00446-019-00347-1
Bender MFarach-Colton MJohnson RMauras SMayer TPhillips CXu HSallinger EVan den Bussche JGeerts F(2017)Write-Optimized Skip ListsProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3034786.3056117(69-78)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3034786.3056117
Zhang DDechev D(2016)An Efficient Lock-Free Logarithmic Search Data Structure Based on Multi-dimensional List2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2016.19(281-292)Online publication date: Jun-2016
https://doi.org/10.1109/ICDCS.2016.19
Dick IFekete AGramoli V(2016)A skip list for multicoreConcurrency and Computation: Practice and Experience10.1002/cpe.387629:4Online publication date: 27-May-2016
https://doi.org/10.1002/cpe.3876
Gramoli V(2015)More than you ever wanted to know about synchronization: synchrobench, measuring the impact of the synchronization on concurrent algorithmsACM SIGPLAN Notices10.1145/2858788.268850150:8(1-10)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2858788.2688501
David TGuerraoui RTrigonakis V(2015)Asynchronized ConcurrencyACM SIGARCH Computer Architecture News10.1145/2786763.269435943:1(631-644)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2786763.2694359
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