---
_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 Press; 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 Press. <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 Press, 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 Press, 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 Press, 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: 2023-09-19T10:44:13Z
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 Press
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...
---
_id: '5966'
abstract:
- lang: eng
  text: 'The transactional conflict problem arises in transactional systems whenever
    two or more concurrent transactions clash on a data item. While the standard solution
    to such conflicts is to immediately abort one of the transactions, some practical
    systems consider the alternative of delaying conflict resolution for a short interval,
    which may allow one of the transactions to commit. The challenge in the transactional
    conflict problem is to choose the optimal length of this delay interval so as
    to minimize the overall running time penalty for the conflicting transactions.
    In this paper, we propose a family of optimal online algorithms for the transactional
    conflict problem. Specifically, we consider variants of this problem which arise
    in different implementations of transactional systems, namely "requestor wins''''
    and "requestor aborts'''' implementations: in the former, the recipient of a coherence
    request is aborted, whereas in the latter, it is the requestor which has to abort.
    Both strategies are implemented by real systems. We show that the requestor aborts
    case can be reduced to a classic instance of the ski rental problem, while the
    requestor wins case leads to a new version of this classical problem, for which
    we derive optimal deterministic and randomized algorithms. Moreover, we prove
    that, under a simplified adversarial model, our algorithms are constant-competitive
    with the offline optimum in terms of throughput. We validate our algorithmic results
    empirically through a hardware simulation of hardware transactional memory (HTM),
    showing that our algorithms can lead to non-trivial performance improvements for
    classic concurrent data structures.'
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: Syed Kamran
  full_name: Haider, Syed Kamran
  last_name: Haider
- first_name: Raphael
  full_name: Kübler, Raphael
  last_name: Kübler
- first_name: Giorgi
  full_name: Nadiradze, Giorgi
  last_name: Nadiradze
citation:
  ama: 'Alistarh D-A, Haider SK, Kübler R, Nadiradze G. The transactional conflict
    problem. In: <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms
    and Architectures  - SPAA ’18</i>. ACM Press; 2018:383-392. doi:<a href="https://doi.org/10.1145/3210377.3210406">10.1145/3210377.3210406</a>'
  apa: 'Alistarh, D.-A., Haider, S. K., Kübler, R., &#38; Nadiradze, G. (2018). The
    transactional conflict problem. In <i>Proceedings of the 30th on Symposium on
    Parallelism in Algorithms and Architectures  - SPAA ’18</i> (pp. 383–392). Vienna,
    Austria: ACM Press. <a href="https://doi.org/10.1145/3210377.3210406">https://doi.org/10.1145/3210377.3210406</a>'
  chicago: Alistarh, Dan-Adrian, Syed Kamran Haider, Raphael Kübler, and Giorgi Nadiradze.
    “The Transactional Conflict Problem.” In <i>Proceedings of the 30th on Symposium
    on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, 383–92. ACM Press,
    2018. <a href="https://doi.org/10.1145/3210377.3210406">https://doi.org/10.1145/3210377.3210406</a>.
  ieee: D.-A. Alistarh, S. K. Haider, R. Kübler, and G. Nadiradze, “The transactional
    conflict problem,” in <i>Proceedings of the 30th on Symposium on Parallelism in
    Algorithms and Architectures  - SPAA ’18</i>, Vienna, Austria, 2018, pp. 383–392.
  ista: 'Alistarh D-A, Haider SK, Kübler R, Nadiradze G. 2018. The transactional conflict
    problem. Proceedings of the 30th on Symposium on Parallelism in Algorithms and
    Architectures  - SPAA ’18. SPAA: Symposium on Parallelism in Algorithms and Architectures,
    383–392.'
  mla: Alistarh, Dan-Adrian, et al. “The Transactional Conflict Problem.” <i>Proceedings
    of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA
    ’18</i>, ACM Press, 2018, pp. 383–92, doi:<a href="https://doi.org/10.1145/3210377.3210406">10.1145/3210377.3210406</a>.
  short: D.-A. Alistarh, S.K. Haider, R. Kübler, G. Nadiradze, in:, Proceedings of
    the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18,
    ACM Press, 2018, pp. 383–392.
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:26:07Z
date_published: 2018-07-16T00:00:00Z
date_updated: 2023-09-19T10:44:49Z
day: '16'
department:
- _id: DaAl
doi: 10.1145/3210377.3210406
external_id:
  arxiv:
  - '1804.00947'
  isi:
  - '000545269600046'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1804.00947
month: '07'
oa: 1
oa_version: Preprint
page: 383-392
publication: Proceedings of the 30th on Symposium on Parallelism in Algorithms and
  Architectures  - SPAA '18
publication_identifier:
  isbn:
  - '9781450357999'
publication_status: published
publisher: ACM Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: The transactional conflict problem
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...