---
_id: '8725'
abstract:
- lang: eng
  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."
acknowledgement: "Vitaly Aksenov: Government of Russian Federation (Grant 08-08).\r\nDan
  Alistarh: ERC Starting Grant 805223 ScaleML."
article_processing_charge: No
arxiv: 1
author:
- first_name: Vitaly
  full_name: Aksenov, Vitaly
  last_name: Aksenov
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: Alexandra
  full_name: Drozdova, Alexandra
  last_name: Drozdova
- first_name: Amirkeivan
  full_name: Mohtashami, Amirkeivan
  last_name: Mohtashami
citation:
  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>'
  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>'
  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.'
  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.
conference:
  end_date: 2020-10-16
  location: Freiburg, Germany
  name: 'DISC: Symposium on Distributed Computing'
  start_date: 2020-10-12
date_created: 2020-11-05T15:26:17Z
date_published: 2020-08-03T00:00:00Z
date_updated: 2023-02-23T13:41:40Z
day: '03'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2020.3
ec_funded: 1
external_id:
  arxiv:
  - '2008.01009'
file:
- access_level: open_access
  checksum: a626a9c47df52b6f6d97edd910dae4ba
  content_type: application/pdf
  creator: dernst
  date_created: 2021-03-11T12:33:35Z
  date_updated: 2021-03-11T12:33:35Z
  file_id: '9237'
  file_name: 2020_LIPIcs_Aksenov.pdf
  file_size: 740358
  relation: main_file
  success: 1
file_date_updated: 2021-03-11T12:33:35Z
has_accepted_license: '1'
intvolume: '       179'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/3.0/
month: '08'
oa: 1
oa_version: Published Version
page: 3:1-3:18
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '805223'
  name: Elastic Coordination for Scalable Machine Learning
publication: 34th International Symposium on Distributed Computing
publication_identifier:
  isbn:
  - '9783959771689'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
series_title: LIPIcs
status: public
title: 'The splay-list: A distribution-adaptive concurrent skip-list'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
  name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
  short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 179
year: '2020'
...