TY - GEN
T1 - Optimal Concurrency for List-Based Sets
AU - Aksenov, Vitaly
AU - Gramoli, Vincent
AU - Kuznetsov, Petr
AU - Shang, Di
AU - Ravi, Srivatsan
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021/1/1
Y1 - 2021/1/1
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/85115309404
U2 - 10.1007/978-3-030-86359-3_29
DO - 10.1007/978-3-030-86359-3_29
M3 - Conference contribution
AN - SCOPUS:85115309404
SN - 9783030863586
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 386
EP - 401
BT - Parallel Computing Technologies - 16th International Conference, PaCT 2021, Proceedings
A2 - Malyshkin, Victor
PB - Springer Science and Business Media Deutschland GmbH
T2 - 16th International Conference on Parallel Computing Technologies, PaCT 2021
Y2 - 13 September 2021 through 18 September 2021
ER -