[{"has_accepted_license":"1","volume":179,"ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2020-10-12","name":"DISC: Symposium on Distributed Computing","end_date":"2020-10-16","location":"Freiburg, Germany"},"date_created":"2020-11-05T15:26:17Z","ddc":["000"],"language":[{"iso":"eng"}],"author":[{"last_name":"Aksenov","first_name":"Vitaly","full_name":"Aksenov, Vitaly"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X"},{"first_name":"Alexandra","full_name":"Drozdova, Alexandra","last_name":"Drozdova"},{"full_name":"Mohtashami, Amirkeivan","first_name":"Amirkeivan","last_name":"Mohtashami"}],"external_id":{"arxiv":["2008.01009"]},"intvolume":"       179","status":"public","tmp":{"name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","short":"CC BY (3.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode"},"page":"3:1-3:18","license":"https://creativecommons.org/licenses/by/3.0/","quality_controlled":"1","title":"The splay-list: A distribution-adaptive concurrent skip-list","date_published":"2020-08-03T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2020","abstract":[{"text":"The design and implementation of efficient concurrent data structures have\r\nseen significant attention. However, most of this work has focused on\r\nconcurrent data structures providing good \\emph{worst-case} guarantees. In real\r\nworkloads, objects are often accessed at different rates, since access\r\ndistributions may be non-uniform. Efficient distribution-adaptive data\r\nstructures are known in the sequential case, e.g. the splay-trees; however,\r\nthey often are hard to translate efficiently in the concurrent case.\r\n  In this paper, we investigate distribution-adaptive concurrent data\r\nstructures and propose a new design called the splay-list. At a high level, the\r\nsplay-list is similar to a standard skip-list, with the key distinction that\r\nthe height of each element adapts dynamically to its access rate: popular\r\nelements ``move up,'' whereas rarely-accessed elements decrease in height. We\r\nshow that the splay-list provides order-optimal amortized complexity bounds for\r\na subset of operations while being amenable to efficient concurrent\r\nimplementation. Experimental results show that the splay-list can leverage\r\ndistribution-adaptivity to improve on the performance of classic concurrent\r\ndesigns, and can outperform the only previously-known distribution-adaptive\r\ndesign in certain settings.","lang":"eng"}],"scopus_import":"1","arxiv":1,"date_updated":"2025-04-14T07:49:12Z","month":"08","file":[{"date_created":"2021-03-11T12:33:35Z","relation":"main_file","access_level":"open_access","creator":"dernst","file_id":"9237","success":1,"date_updated":"2021-03-11T12:33:35Z","file_size":740358,"file_name":"2020_LIPIcs_Aksenov.pdf","checksum":"a626a9c47df52b6f6d97edd910dae4ba","content_type":"application/pdf"}],"oa_version":"Published Version","publication_status":"published","article_processing_charge":"No","project":[{"grant_number":"805223","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"series_title":"LIPIcs","oa":1,"department":[{"_id":"DaAl"}],"citation":{"chicago":"Aksenov, Vitaly, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” In <i>34th International Symposium on Distributed Computing</i>, 179:3:1-3:18. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.3\">https://doi.org/10.4230/LIPIcs.DISC.2020.3</a>.","ieee":"V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list: A distribution-adaptive concurrent skip-list,” in <i>34th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2020, vol. 179, p. 3:1-3:18.","ista":"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.","apa":"Aksenov, V., Alistarh, D.-A., Drozdova, A., &#38; Mohtashami, A. (2020). The splay-list: A distribution-adaptive concurrent skip-list. In <i>34th International Symposium on Distributed Computing</i> (Vol. 179, p. 3:1-3:18). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.3\">https://doi.org/10.4230/LIPIcs.DISC.2020.3</a>","ama":"Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive concurrent skip-list. In: <i>34th International Symposium on Distributed Computing</i>. Vol 179. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020:3:1-3:18. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.3\">10.4230/LIPIcs.DISC.2020.3</a>","mla":"Aksenov, Vitaly, et al. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” <i>34th International Symposium on Distributed Computing</i>, vol. 179, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 3:1-3:18, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.3\">10.4230/LIPIcs.DISC.2020.3</a>.","short":"V. Aksenov, D.-A. Alistarh, A. Drozdova, A. Mohtashami, in:, 34th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 3:1-3:18."},"type":"conference","doi":"10.4230/LIPIcs.DISC.2020.3","publication_identifier":{"isbn":["9783959771689"],"issn":["1868-8969"]},"acknowledgement":"Vitaly Aksenov: Government of Russian Federation (Grant 08-08).\r\nDan Alistarh: ERC Starting Grant 805223 ScaleML.","day":"03","_id":"8725","file_date_updated":"2021-03-11T12:33:35Z","publication":"34th International Symposium on Distributed Computing"}]