---
res:
  bibo_abstract:
  - 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.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Dan-Adrian
      foaf_name: Alistarh, Dan-Adrian
      foaf_surname: Alistarh
      foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0003-3650-940X
  - foaf_Person:
      foaf_givenName: Trevor A
      foaf_name: Brown, Trevor A
      foaf_surname: Brown
      foaf_workInfoHomepage: http://www.librecat.org/personId=3569F0A0-F248-11E8-B48F-1D18A9856A87
  - foaf_Person:
      foaf_givenName: Justin
      foaf_name: Kopinsky, Justin
      foaf_surname: Kopinsky
  - foaf_Person:
      foaf_givenName: Jerry Z.
      foaf_name: Li, Jerry Z.
      foaf_surname: Li
  - foaf_Person:
      foaf_givenName: Giorgi
      foaf_name: Nadiradze, Giorgi
      foaf_surname: Nadiradze
  bibo_doi: 10.1145/3210377.3210411
  dct_date: 2018^xs_gYear
  dct_identifier:
  - UT:000545269600016
  dct_isPartOf:
  - http://id.crossref.org/issn/9781450357999
  dct_language: eng
  dct_publisher: ACM@
  dct_title: Distributionally linearizable data structures@
...