The splay-list: A distribution-adaptive concurrent skip-list

Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. 2020. The splay-list: A distribution-adaptive concurrent skip-list. 34th International Symposium on Distributed Computing. DISC: Symposium on Distributed ComputingLIPIcs vol. 179, 3:1-3:18.

Download
OA 2020_LIPIcs_Aksenov.pdf 740.36 KB

Conference Paper | Published | English
Author
Aksenov, Vitaly; Alistarh, Dan-AdrianIST Austria; Drozdova, Alexandra; Mohtashami, Amirkeivan
Department
Abstract
The design and implementation of efficient concurrent data structures have seen significant attention. However, most of this work has focused on concurrent data structures providing good \emph{worst-case} guarantees. In real workloads, objects are often accessed at different rates, since access distributions may be non-uniform. Efficient distribution-adaptive data structures are known in the sequential case, e.g. the splay-trees; however, they often are hard to translate efficiently in the concurrent case. In this paper, 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. Experimental results show that the splay-list can leverage distribution-adaptivity to improve on the performance of classic concurrent designs, and can outperform the only previously-known distribution-adaptive design in certain settings.
Publishing Year
Date Published
2020-08-03
Proceedings Title
34th International Symposium on Distributed Computing
Acknowledgement
Vitaly Aksenov: Government of Russian Federation (Grant 08-08). Dan Alistarh: ERC Starting Grant 805223 ScaleML.
Volume
179
Page
3:1-3:18
Conference
DISC: Symposium on Distributed Computing
Conference Location
Freiburg, Germany
Conference Date
2020-10-12 – 2020-10-16
ISSN
IST-REx-ID

Cite this

Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive concurrent skip-list. In: 34th International Symposium on Distributed Computing. Vol 179. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020:3:1-3:18. doi:10.4230/LIPIcs.DISC.2020.3
Aksenov, V., Alistarh, D.-A., Drozdova, A., & Mohtashami, A. (2020). The splay-list: A distribution-adaptive concurrent skip-list. In 34th International Symposium on Distributed Computing (Vol. 179, p. 3:1-3:18). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2020.3
Aksenov, Vitaly, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” In 34th International Symposium on Distributed Computing, 179:3:1-3:18. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.DISC.2020.3.
V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list: A distribution-adaptive concurrent skip-list,” in 34th International Symposium on Distributed Computing, Freiburg, Germany, 2020, vol. 179, p. 3:1-3:18.
Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. 2020. The splay-list: A distribution-adaptive concurrent skip-list. 34th International Symposium on Distributed Computing. DISC: Symposium on Distributed ComputingLIPIcs vol. 179, 3:1-3:18.
Aksenov, Vitaly, et al. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” 34th International Symposium on Distributed Computing, vol. 179, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 3:1-3:18, doi:10.4230/LIPIcs.DISC.2020.3.
All files available under the following license(s):
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2021-03-11
MD5 Checksum
a626a9c47df52b6f6d97edd910dae4ba


Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 2008.01009

Search this title in

Google Scholar
ISBN Search