article published yes Vitalii Aksenov author 2980135A-F248-11E8-B48F-1D18A9856A87 Dan-Adrian Alistarh author 4A899BFC-F248-11E8-B48F-1D18A9856A870000-0003-3650-940X Alexandra Drozdova author Amirkeivan Mohtashami author DaAl department The design and implementation of efficient concurrent data structures has seen significant attention. However, most of this work has focused on concurrent data structures providing good worst-case guarantees, although, in real workloads, objects are often accessed at different rates. Efficient distribution-adaptive data structures, such as splay-trees, are known in the sequential case; however, they often are hard to translate efficiently to the concurrent case. We investigate distribution-adaptive concurrent data structures, and propose a new design called the splay-list. At a high level, the splay-list is similar to a standard skip-list, with the key distinction that the height of each element adapts dynamically to its access rate: popular elements “move up,” whereas rarely-accessed elements decrease in height. We show that the splay-list provides order-optimal amortized complexity bounds for a subset of operations, while being amenable to efficient concurrent implementation. Experiments show that the splay-list can leverage distribution-adaptivity for performance, and can outperform the only previously-known distribution-adaptive concurrent design in certain workloads. Springer Nature2023 eng 0178-2770 1432-0452 2008.01009 00091342400000110.1007/s00446-022-00441-x 36395-418 Aksenov, Vitalii, et al. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” <i>Distributed Computing</i>, vol. 36, Springer Nature, 2023, pp. 395–418, doi:<a href="https://doi.org/10.1007/s00446-022-00441-x">10.1007/s00446-022-00441-x</a>. V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list: A distribution-adaptive concurrent skip-list,” <i>Distributed Computing</i>, vol. 36. Springer Nature, pp. 395–418, 2023. Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive concurrent skip-list. <i>Distributed Computing</i>. 2023;36:395-418. doi:<a href="https://doi.org/10.1007/s00446-022-00441-x">10.1007/s00446-022-00441-x</a> Aksenov, V., Alistarh, D.-A., Drozdova, A., &#38; Mohtashami, A. (2023). The splay-list: A distribution-adaptive concurrent skip-list. <i>Distributed Computing</i>. Springer Nature. <a href="https://doi.org/10.1007/s00446-022-00441-x">https://doi.org/10.1007/s00446-022-00441-x</a> Aksenov, Vitalii, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” <i>Distributed Computing</i>. Springer Nature, 2023. <a href="https://doi.org/10.1007/s00446-022-00441-x">https://doi.org/10.1007/s00446-022-00441-x</a>. V. Aksenov, D.-A. Alistarh, A. Drozdova, A. Mohtashami, Distributed Computing 36 (2023) 395–418. Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. 2023. The splay-list: A distribution-adaptive concurrent skip-list. Distributed Computing. 36, 395–418. 123302023-01-22T23:00:55Z2023-08-14T12:54:32Z