---
_id: '12164'
abstract:
- lang: eng
  text: 'A shared-memory counter is a widely-used and well-studied concurrent object.
    It supports two operations: An Inc operation that increases its value by 1 and
    a Read operation that returns its current value. In Jayanti et al (SIAM J Comput,
    30(2), 2000), Jayanti, Tan and Toueg proved a linear lower bound on the worst-case
    step complexity of obstruction-free implementations, from read-write registers,
    of a large class of shared objects that includes counters. The lower bound leaves
    open the question of finding counter implementations with sub-linear amortized
    step complexity. In this work, we address this gap. We show that n-process, wait-free
    and linearizable counters can be implemented from read-write registers with O(log2n)
    amortized step complexity. This is the first counter algorithm from read-write
    registers that provides sub-linear amortized step complexity in executions of
    arbitrary length. Since a logarithmic lower bound on the amortized step complexity
    of obstruction-free counter implementations exists, our upper bound is within
    a logarithmic factor of the optimal. The worst-case step complexity of the construction
    remains linear, which is optimal. This is obtained thanks to a new max register
    construction with O(logn) amortized step complexity in executions of arbitrary
    length in which the value stored in the register does not grow too quickly. We
    then leverage an existing counter algorithm by Aspnes, Attiya and Censor-Hillel
    [1] in which we “plug” our max register implementation to show that it remains
    linearizable while achieving O(log2n) amortized step complexity.'
acknowledgement: A preliminary version of this work appeared in DISC’19. Mirza Ahad
  Baig, Alessia Milani and Corentin Travers are supported by ANR projects Descartes
  and FREDDA. Mirza Ahad Baig is supported by UMI Relax. Danny Hendler is supported
  by the Israel Science Foundation (Grants 380/18 and 1425/22).
article_processing_charge: No
article_type: original
author:
- first_name: Mirza Ahad
  full_name: Baig, Mirza Ahad
  id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
  last_name: Baig
- first_name: Danny
  full_name: Hendler, Danny
  last_name: Hendler
- first_name: Alessia
  full_name: Milani, Alessia
  last_name: Milani
- first_name: Corentin
  full_name: Travers, Corentin
  last_name: Travers
citation:
  ama: Baig MA, Hendler D, Milani A, Travers C. Long-lived counters with polylogarithmic
    amortized step complexity. <i>Distributed Computing</i>. 2023;36:29-43. doi:<a
    href="https://doi.org/10.1007/s00446-022-00439-5">10.1007/s00446-022-00439-5</a>
  apa: Baig, M. A., Hendler, D., Milani, A., &#38; Travers, C. (2023). Long-lived
    counters with polylogarithmic amortized step complexity. <i>Distributed Computing</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s00446-022-00439-5">https://doi.org/10.1007/s00446-022-00439-5</a>
  chicago: Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers.
    “Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” <i>Distributed
    Computing</i>. Springer Nature, 2023. <a href="https://doi.org/10.1007/s00446-022-00439-5">https://doi.org/10.1007/s00446-022-00439-5</a>.
  ieee: M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived counters with
    polylogarithmic amortized step complexity,” <i>Distributed Computing</i>, vol.
    36. Springer Nature, pp. 29–43, 2023.
  ista: Baig MA, Hendler D, Milani A, Travers C. 2023. Long-lived counters with polylogarithmic
    amortized step complexity. Distributed Computing. 36, 29–43.
  mla: Baig, Mirza Ahad, et al. “Long-Lived Counters with Polylogarithmic Amortized
    Step Complexity.” <i>Distributed Computing</i>, vol. 36, Springer Nature, 2023,
    pp. 29–43, doi:<a href="https://doi.org/10.1007/s00446-022-00439-5">10.1007/s00446-022-00439-5</a>.
  short: M.A. Baig, D. Hendler, A. Milani, C. Travers, Distributed Computing 36 (2023)
    29–43.
date_created: 2023-01-12T12:10:08Z
date_published: 2023-03-01T00:00:00Z
date_updated: 2023-08-16T08:39:36Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/s00446-022-00439-5
external_id:
  isi:
  - '000890138700001'
intvolume: '        36'
isi: 1
keyword:
- Computational Theory and Mathematics
- Computer Networks and Communications
- Hardware and Architecture
- Theoretical Computer Science
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://drops.dagstuhl.de/opus/volltexte/2019/11310/
month: '03'
oa: 1
oa_version: Preprint
page: 29-43
publication: Distributed Computing
publication_identifier:
  eissn:
  - 1432-0452
  issn:
  - 0178-2770
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Long-lived counters with polylogarithmic amortized step complexity
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2023'
...
---
_id: '12330'
abstract:
- lang: eng
  text: 'The design and implementation of efficient concurrent data structures has
    seen significant attention. However, most of this work has focused on concurrent
    data structures providing good worst-case guarantees, although, in real workloads,
    objects are often accessed at different rates. Efficient distribution-adaptive
    data structures, such as splay-trees, are known in the sequential case; however,
    they often are hard to translate efficiently to the concurrent case. We investigate
    distribution-adaptive concurrent data structures, and propose a new design called
    the splay-list. At a high level, the splay-list is similar to a standard skip-list,
    with the key distinction that the height of each element adapts dynamically to
    its access rate: popular elements “move up,” whereas rarely-accessed elements
    decrease in height. We show that the splay-list provides order-optimal amortized
    complexity bounds for a subset of operations, while being amenable to efficient
    concurrent implementation. Experiments show that the splay-list can leverage distribution-adaptivity
    for performance, and can outperform the only previously-known distribution-adaptive
    concurrent design in certain workloads.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Vitalii
  full_name: Aksenov, Vitalii
  id: 2980135A-F248-11E8-B48F-1D18A9856A87
  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. <i>Distributed Computing</i>. 2023;36:395-418. doi:<a href="https://doi.org/10.1007/s00446-022-00441-x">10.1007/s00446-022-00441-x</a>'
  apa: 'Aksenov, V., Alistarh, D.-A., Drozdova, A., &#38; Mohtashami, A. (2023). The
    splay-list: A distribution-adaptive concurrent skip-list. <i>Distributed Computing</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s00446-022-00441-x">https://doi.org/10.1007/s00446-022-00441-x</a>'
  chicago: 'Aksenov, Vitalii, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan
    Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” <i>Distributed
    Computing</i>. Springer Nature, 2023. <a href="https://doi.org/10.1007/s00446-022-00441-x">https://doi.org/10.1007/s00446-022-00441-x</a>.'
  ieee: 'V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list:
    A distribution-adaptive concurrent skip-list,” <i>Distributed Computing</i>, vol.
    36. Springer Nature, pp. 395–418, 2023.'
  ista: 'Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. 2023. The splay-list:
    A distribution-adaptive concurrent skip-list. Distributed Computing. 36, 395–418.'
  mla: 'Aksenov, Vitalii, et al. “The Splay-List: A Distribution-Adaptive Concurrent
    Skip-List.” <i>Distributed Computing</i>, vol. 36, Springer Nature, 2023, pp.
    395–418, doi:<a href="https://doi.org/10.1007/s00446-022-00441-x">10.1007/s00446-022-00441-x</a>.'
  short: V. Aksenov, D.-A. Alistarh, A. Drozdova, A. Mohtashami, Distributed Computing
    36 (2023) 395–418.
date_created: 2023-01-22T23:00:55Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2025-07-22T14:06:00Z
day: '01'
department:
- _id: DaAl
doi: 10.1007/s00446-022-00441-x
external_id:
  arxiv:
  - '2008.01009'
  isi:
  - '000913424000001'
  oaworkID:
  - w4390499170
intvolume: '        36'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2008.01009
month: '09'
oa: 1
oa_version: Preprint
oaworkID: 1
page: 395-418
publication: Distributed Computing
publication_identifier:
  eissn:
  - 1432-0452
  issn:
  - 0178-2770
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The splay-list: A distribution-adaptive concurrent skip-list'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2023'
...
---
_id: '7939'
abstract:
- lang: eng
  text: "We design fast deterministic algorithms for distance computation in the Congested
    Clique model. Our key contributions include:\r\n    A (2+ϵ)-approximation for
    all-pairs shortest paths in O(log2n/ϵ) rounds on unweighted undirected graphs.
    With a small additional additive factor, this also applies for weighted graphs.
    This is the first sub-polynomial constant-factor approximation for APSP in this
    model.\r\n    A (1+ϵ)-approximation for multi-source shortest paths from O(n−−√)
    sources in O(log2n/ϵ) rounds on weighted undirected graphs. This is the first
    sub-polynomial algorithm obtaining this approximation for a set of sources of
    polynomial size.\r\n\r\nOur main techniques are new distance tools that are obtained
    via improved algorithms for sparse matrix multiplication, which we leverage to
    construct efficient hopsets and shortest paths. Furthermore, our techniques extend
    to additional distance problems for which we improve upon the state-of-the-art,
    including diameter approximation, and an exact single-source shortest paths algorithm
    for weighted undirected graphs in O~(n1/6) rounds. "
acknowledgement: Open access funding provided by Institute of Science and Technology
  (IST Austria). We thank Mohsen Ghaffari, Michael Elkin and Merav Parter for fruitful
  discussions. This project has received funding from the European Union’s Horizon
  2020 Research And Innovation Program under Grant Agreement No. 755839.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Keren
  full_name: Censor-Hillel, Keren
  last_name: Censor-Hillel
- first_name: Michal
  full_name: Dory, Michal
  last_name: Dory
- first_name: Janne
  full_name: Korhonen, Janne
  id: C5402D42-15BC-11E9-A202-CA2BE6697425
  last_name: Korhonen
- first_name: Dean
  full_name: Leitersdorf, Dean
  last_name: Leitersdorf
citation:
  ama: Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. Fast approximate shortest
    paths in the congested clique. <i>Distributed Computing</i>. 2021;34:463-487.
    doi:<a href="https://doi.org/10.1007/s00446-020-00380-5">10.1007/s00446-020-00380-5</a>
  apa: Censor-Hillel, K., Dory, M., Korhonen, J., &#38; Leitersdorf, D. (2021). Fast
    approximate shortest paths in the congested clique. <i>Distributed Computing</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s00446-020-00380-5">https://doi.org/10.1007/s00446-020-00380-5</a>
  chicago: Censor-Hillel, Keren, Michal Dory, Janne Korhonen, and Dean Leitersdorf.
    “Fast Approximate Shortest Paths in the Congested Clique.” <i>Distributed Computing</i>.
    Springer Nature, 2021. <a href="https://doi.org/10.1007/s00446-020-00380-5">https://doi.org/10.1007/s00446-020-00380-5</a>.
  ieee: K. Censor-Hillel, M. Dory, J. Korhonen, and D. Leitersdorf, “Fast approximate
    shortest paths in the congested clique,” <i>Distributed Computing</i>, vol. 34.
    Springer Nature, pp. 463–487, 2021.
  ista: Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. 2021. Fast approximate
    shortest paths in the congested clique. Distributed Computing. 34, 463–487.
  mla: Censor-Hillel, Keren, et al. “Fast Approximate Shortest Paths in the Congested
    Clique.” <i>Distributed Computing</i>, vol. 34, Springer Nature, 2021, pp. 463–87,
    doi:<a href="https://doi.org/10.1007/s00446-020-00380-5">10.1007/s00446-020-00380-5</a>.
  short: K. Censor-Hillel, M. Dory, J. Korhonen, D. Leitersdorf, Distributed Computing
    34 (2021) 463–487.
date_created: 2020-06-07T22:00:54Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2024-03-07T14:43:39Z
day: '01'
department:
- _id: DaAl
doi: 10.1007/s00446-020-00380-5
external_id:
  arxiv:
  - '1903.05956'
  isi:
  - '000556444600001'
intvolume: '        34'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1007/s00446-020-00380-5
month: '12'
oa: 1
oa_version: Published Version
page: 463-487
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
  name: IST Austria Open Access Fund
publication: Distributed Computing
publication_identifier:
  eissn:
  - 1432-0452
  issn:
  - 0178-2770
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '6933'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Fast approximate shortest paths in the congested clique
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2021'
...
---
_id: '7150'
abstract:
- lang: eng
  text: "In this work, we use algebraic methods for studying distance computation
    and subgraph detection tasks in the congested clique model. Specifically, we adapt
    parallel matrix multiplication implementations to the congested clique, obtaining
    an O(n1−2/ω) round matrix multiplication algorithm, where ω<2.3728639 is the exponent
    of matrix multiplication. In conjunction with known techniques from centralised
    algorithmics, this gives significant improvements over previous best upper bounds
    in the congested clique model. The highlight results include:\r\n\r\n1.    triangle
    and 4-cycle counting in O(n0.158) rounds, improving upon the O(n1/3) algorithm
    of Dolev et al. [DISC 2012],\r\n2. a (1+o(1))-approximation of all-pairs shortest
    paths in O(n0.158) rounds, improving upon the O~(n1/2)-round (2+o(1))-approximation
    algorithm given by Nanongkai [STOC 2014], and\r\n 3. computing the girth in O(n0.158)
    rounds, which is the first non-trivial solution in this model.\r\n   \r\nIn addition,
    we present a novel constant-round combinatorial algorithm for detecting 4-cycles."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Keren
  full_name: Censor-Hillel, Keren
  last_name: Censor-Hillel
- first_name: Petteri
  full_name: Kaski, Petteri
  last_name: Kaski
- first_name: Janne
  full_name: Korhonen, Janne
  id: C5402D42-15BC-11E9-A202-CA2BE6697425
  last_name: Korhonen
- first_name: Christoph
  full_name: Lenzen, Christoph
  last_name: Lenzen
- first_name: Ami
  full_name: Paz, Ami
  last_name: Paz
- first_name: Jukka
  full_name: Suomela, Jukka
  last_name: Suomela
citation:
  ama: Censor-Hillel K, Kaski P, Korhonen J, Lenzen C, Paz A, Suomela J. Algebraic
    methods in the congested clique. <i>Distributed Computing</i>. 2019;32(6):461-478.
    doi:<a href="https://doi.org/10.1007/s00446-016-0270-2">10.1007/s00446-016-0270-2</a>
  apa: Censor-Hillel, K., Kaski, P., Korhonen, J., Lenzen, C., Paz, A., &#38; Suomela,
    J. (2019). Algebraic methods in the congested clique. <i>Distributed Computing</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s00446-016-0270-2">https://doi.org/10.1007/s00446-016-0270-2</a>
  chicago: Censor-Hillel, Keren, Petteri Kaski, Janne Korhonen, Christoph Lenzen,
    Ami Paz, and Jukka Suomela. “Algebraic Methods in the Congested Clique.” <i>Distributed
    Computing</i>. Springer Nature, 2019. <a href="https://doi.org/10.1007/s00446-016-0270-2">https://doi.org/10.1007/s00446-016-0270-2</a>.
  ieee: K. Censor-Hillel, P. Kaski, J. Korhonen, C. Lenzen, A. Paz, and J. Suomela,
    “Algebraic methods in the congested clique,” <i>Distributed Computing</i>, vol.
    32, no. 6. Springer Nature, pp. 461–478, 2019.
  ista: Censor-Hillel K, Kaski P, Korhonen J, Lenzen C, Paz A, Suomela J. 2019. Algebraic
    methods in the congested clique. Distributed Computing. 32(6), 461–478.
  mla: Censor-Hillel, Keren, et al. “Algebraic Methods in the Congested Clique.” <i>Distributed
    Computing</i>, vol. 32, no. 6, Springer Nature, 2019, pp. 461–78, doi:<a href="https://doi.org/10.1007/s00446-016-0270-2">10.1007/s00446-016-0270-2</a>.
  short: K. Censor-Hillel, P. Kaski, J. Korhonen, C. Lenzen, A. Paz, J. Suomela, Distributed
    Computing 32 (2019) 461–478.
date_created: 2019-12-05T09:49:49Z
date_published: 2019-12-01T00:00:00Z
date_updated: 2021-01-12T08:12:05Z
day: '01'
doi: 10.1007/s00446-016-0270-2
extern: '1'
external_id:
  arxiv:
  - '1503.04963'
intvolume: '        32'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1503.04963
month: '12'
oa: 1
oa_version: Preprint
page: 461-478
publication: Distributed Computing
publication_identifier:
  issn:
  - 0178-2770
  - 1432-0452
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Algebraic methods in the congested clique
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 32
year: '2019'
...