---
_id: '5965'
abstract:
- lang: eng
  text: Relaxed concurrent data structures have become increasingly popular, due to
    their scalability in graph processing and machine learning applications (\citeNguyen13,
    gonzalez2012powergraph ). Despite considerable interest, there exist families
    of natural, high performing randomized relaxed concurrent data structures, such
    as the popular MultiQueue~\citeMQ pattern for implementing relaxed priority queue
    data structures, for which no guarantees are known in the concurrent setting~\citeAKLN17.
    Our main contribution is in showing for the first time that, under a set of analytic
    assumptions, a family of relaxed concurrent data structures, including variants
    of MultiQueues, but also a new approximate counting algorithm we call the MultiCounter,
    provides strong probabilistic guarantees on the degree of relaxation with respect
    to the sequential specification, in arbitrary concurrent executions. We formalize
    these guarantees via a new correctness condition called distributional linearizability,
    tailored to concurrent implementations with randomized relaxations. Our result
    is based on a new analysis of an asynchronous variant of the classic power-of-two-choices
    load balancing algorithm, in which placement choices can be based on inconsistent,
    outdated information (this result may be of independent interest). We validate
    our results empirically, showing that the MultiCounter algorithm can implement
    scalable relaxed timestamps.
article_processing_charge: No
arxiv: 1
author:
- 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: Trevor A
  full_name: Brown, Trevor A
  id: 3569F0A0-F248-11E8-B48F-1D18A9856A87
  last_name: Brown
- first_name: Justin
  full_name: Kopinsky, Justin
  last_name: Kopinsky
- first_name: Jerry Z.
  full_name: Li, Jerry Z.
  last_name: Li
- first_name: Giorgi
  full_name: Nadiradze, Giorgi
  last_name: Nadiradze
citation:
  ama: 'Alistarh D-A, Brown TA, Kopinsky J, Li JZ, Nadiradze G. Distributionally linearizable
    data structures. In: <i>Proceedings of the 30th on Symposium on Parallelism in
    Algorithms and Architectures  - SPAA ’18</i>. ACM; 2018:133-142. doi:<a href="https://doi.org/10.1145/3210377.3210411">10.1145/3210377.3210411</a>'
  apa: 'Alistarh, D.-A., Brown, T. A., Kopinsky, J., Li, J. Z., &#38; Nadiradze, G.
    (2018). Distributionally linearizable data structures. In <i>Proceedings of the
    30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>
    (pp. 133–142). Vienna, Austria: ACM. <a href="https://doi.org/10.1145/3210377.3210411">https://doi.org/10.1145/3210377.3210411</a>'
  chicago: Alistarh, Dan-Adrian, Trevor A Brown, Justin Kopinsky, Jerry Z. Li, and
    Giorgi Nadiradze. “Distributionally Linearizable Data Structures.” In <i>Proceedings
    of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA
    ’18</i>, 133–42. ACM, 2018. <a href="https://doi.org/10.1145/3210377.3210411">https://doi.org/10.1145/3210377.3210411</a>.
  ieee: D.-A. Alistarh, T. A. Brown, J. Kopinsky, J. Z. Li, and G. Nadiradze, “Distributionally
    linearizable data structures,” in <i>Proceedings of the 30th on Symposium on Parallelism
    in Algorithms and Architectures  - SPAA ’18</i>, Vienna, Austria, 2018, pp. 133–142.
  ista: 'Alistarh D-A, Brown TA, Kopinsky J, Li JZ, Nadiradze G. 2018. Distributionally
    linearizable data structures. Proceedings of the 30th on Symposium on Parallelism
    in Algorithms and Architectures  - SPAA ’18. SPAA: Symposium on Parallelism in
    Algorithms and Architectures, 133–142.'
  mla: Alistarh, Dan-Adrian, et al. “Distributionally Linearizable Data Structures.”
    <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures 
    - SPAA ’18</i>, ACM, 2018, pp. 133–42, doi:<a href="https://doi.org/10.1145/3210377.3210411">10.1145/3210377.3210411</a>.
  short: D.-A. Alistarh, T.A. Brown, J. Kopinsky, J.Z. Li, G. Nadiradze, in:, Proceedings
    of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA
    ’18, ACM, 2018, pp. 133–142.
conference:
  end_date: 2018-07-18
  location: Vienna, Austria
  name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures'
  start_date: 2018-07-16
date_created: 2019-02-13T10:17:19Z
date_published: 2018-07-16T00:00:00Z
date_updated: 2026-04-08T07:00:45Z
day: '16'
department:
- _id: DaAl
doi: 10.1145/3210377.3210411
external_id:
  arxiv:
  - '1804.01018'
  isi:
  - '000545269600016'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1804.01018
month: '07'
oa: 1
oa_version: Preprint
page: 133-142
publication: Proceedings of the 30th on Symposium on Parallelism in Algorithms and
  Architectures  - SPAA '18
publication_identifier:
  isbn:
  - '9781450357999'
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
  record:
  - id: '10429'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Distributionally linearizable data structures
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...