Optimal Concurrency for List-Based Sets
Authors: 
Vitaly Aksenov, 
Vincent Gramoli, Petr Kuznetsov, Di Shang, Srivatsan RaviAuthors Info & Claims
Pages 386 - 401
Abstract
Designing an efficient concurrent data structure is a challenge that is not easy to meet. Intuitively, efficiency of an implementation is defined, in the first place, by its ability to process applied operations in parallel, without using unnecessary synchronization. As we show in this paper, even for a data structure as simple as a linked list used to implement the set type, the most efficient algorithms known so far are not concurrency-optimal: they may reject correct concurrent schedules. We propose a new algorithm for the list-based set based on a value-aware try-lock that we show to achieve optimal concurrency: it only rejects concurrent schedules that violate correctness of the implemented set type. We show that reaching this kind of optimality may be beneficial in practice. Our concurrency-optimal list-based set outperforms two state-of-the-art algorithms: the Lazy Linked List and the Harris-Michael List.
References
[1]
Gramoli V, Kuznetsov P, and Ravi S Suomela J In the search for optimal concurrency Structural Information and Communication Complexity 2016 Cham Springer 143-158
[2]
Sutter, H.: Choose concurrency-friendly data structures. Dr. Dobb’s J. (2008)
[3]
Heller S, Herlihy M, Luchangco V, Moir M, Scherer WN, and Shavit N Anderson JH, Prencipe G, and Wattenhofer R A lazy concurrent list-based set algorithm Principles of Distributed Systems 2006 Heidelberg Springer 3-16
[4]
Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann (2012)
[5]
Harris TL Welch J A pragmatic implementation of non-blocking linked-lists Distributed Computing 2001 Heidelberg Springer 300-314
[6]
Michael, M.M.: High performance dynamic lock-free hash tables and list-based sets. In: SPAA, pp. 73–82 (2002)
[7]
Guerraoui, R., Kapalka, M.: Principles of Transactional Memory, Synthesis Lectures on Distributed Computing Theory. Morgan and Claypool (2010)
[8]
Herlihy M and Wing JM Linearizability: a correctness condition for concurrent objects ACM Trans. Program. Lang. Syst. 1990 12 3 463-492
[9]
Aksenov V, Gramoli V, Kuznetsov P, Malova A, and Ravi S Rivera FF, Pena TF, and Cabaleiro JC A concurrency-optimal binary search tree Euro-Par 2017: Parallel Processing 2017 Cham Springer 580-593
[10]
Aksenov, V., Gramoli, V., Kuznetsov, P., Ravi, S., Shang, D.: A concurrency-optimal list-based set. CoRR abs/1502.01633 (2021)
[11]
Gramoli, V.: More than you ever wanted to know about synchronization: synchrobench, measuring the impact of the synchronization on concurrent algorithms. In: PPoPP, pp. 1–10 (2015)
[12]
Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann (1996)
[13]
Sun Microsystems: Memory Management in the Java HotSpot Virtual Machine, April 2006. http://www.oracle.com/technetwork/java/javase/memorymanagement-whitepaper-150215.pdf
[14]
Fomitchev, M., Ruppert, E.: Lock-free linked lists and skip lists. In: PODC, pp. 50–59 (2004)
[15]
Gibson J and Gramoli V Moses Y Why non-blocking operations should be selfish Distributed Computing 2015 Heidelberg Springer 200-214
[16]
Kung, H.T., Papadimitriou, C.H.: An optimality theory of concurrency control for databases. In: SIGMOD, pp. 116–126 (1979)
[17]
Herlihy M Apologizing versus asking permission: optimistic concurrency control for abstract data types ACM Trans. Database Syst. 1990 15 1 96-124
[18]
Weihl WE Commutativity-based concurrency control for abstract data types IEEE Trans. Comput. 1988 37 12 1488-1505
[19]
Guerraoui R, Henzinger TA, and Singh V Taubenfeld G Permissiveness in transactional memories Distributed Computing 2008 Heidelberg Springer 305-319
[20]
Gramoli V, Harmanci D, and Felber P On the input acceptance of transactional memory Parallel Process. Lett. 2010 20 1 31-50
[21]
Haas, A., et al.: Local linearizability for concurrent container-type data structures. In: CONCUR 2016, vol. 59, pp. 6:1–6:15 (2016)
[22]
David, T., Guerraoui, R., Trigonakis, V.: Asynchronized concurrency: the secret to scaling concurrent search data structures. In: ASPLOS, pp. 631–644 (2015)
Index Terms
- Optimal Concurrency for List-Based Sets
Index terms have been assigned to the content through auto-classification.
Recommendations
Semantics-based concurrency control: beyond commutativity
The concurrency of transactions executing on atomic data types can be enhanced through the use of semantic information about operations defined on these types. Hitherto, commutativity of operations has been exploited to provide enchanced concurrency ...
Relationships between covering-based rough sets and relation-based rough sets
Rough set theory is an important technique to deal with vagueness and granularity in information systems. In rough set theory, relation-based rough sets and covering-based rough sets are two important extensions of the classical rough sets. This paper ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© Springer Nature Switzerland AG 2021.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 13 September 2021
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Dec 2024