---
_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
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. Distributed Computing. 2023;36:395-418. doi:10.1007/s00446-022-00441-x'
apa: 'Aksenov, V., Alistarh, D.-A., Drozdova, A., & Mohtashami, A. (2023). The
splay-list: A distribution-adaptive concurrent skip-list. Distributed Computing.
Springer Nature. https://doi.org/10.1007/s00446-022-00441-x'
chicago: 'Aksenov, Vitalii, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan
Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” Distributed
Computing. Springer Nature, 2023. https://doi.org/10.1007/s00446-022-00441-x.'
ieee: 'V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list:
A distribution-adaptive concurrent skip-list,” Distributed Computing, 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.” Distributed Computing, vol. 36, Springer Nature, 2023, pp.
395–418, doi:10.1007/s00446-022-00441-x.'
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: 2023-08-14T12:54:32Z
day: '01'
department:
- _id: DaAl
doi: 10.1007/s00446-022-00441-x
external_id:
arxiv:
- '2008.01009'
isi:
- '000913424000001'
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
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: '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. Distributed Computing. 2023;36:29-43. doi:10.1007/s00446-022-00439-5
apa: Baig, M. A., Hendler, D., Milani, A., & Travers, C. (2023). Long-lived
counters with polylogarithmic amortized step complexity. Distributed Computing.
Springer Nature. https://doi.org/10.1007/s00446-022-00439-5
chicago: Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers.
“Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” Distributed
Computing. Springer Nature, 2023. https://doi.org/10.1007/s00446-022-00439-5.
ieee: M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived counters with
polylogarithmic amortized step complexity,” Distributed Computing, 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.” Distributed Computing, vol. 36, Springer Nature, 2023,
pp. 29–43, doi:10.1007/s00446-022-00439-5.
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: '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
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. Distributed Computing. 2021;34:463-487.
doi:10.1007/s00446-020-00380-5
apa: Censor-Hillel, K., Dory, M., Korhonen, J., & Leitersdorf, D. (2021). Fast
approximate shortest paths in the congested clique. Distributed Computing.
Springer Nature. https://doi.org/10.1007/s00446-020-00380-5
chicago: Censor-Hillel, Keren, Michal Dory, Janne Korhonen, and Dean Leitersdorf.
“Fast Approximate Shortest Paths in the Congested Clique.” Distributed Computing.
Springer Nature, 2021. https://doi.org/10.1007/s00446-020-00380-5.
ieee: K. Censor-Hillel, M. Dory, J. Korhonen, and D. Leitersdorf, “Fast approximate
shortest paths in the congested clique,” Distributed Computing, 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.” Distributed Computing, vol. 34, Springer Nature, 2021, pp. 463–87,
doi:10.1007/s00446-020-00380-5.
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
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. Distributed Computing. 2019;32(6):461-478.
doi:10.1007/s00446-016-0270-2
apa: Censor-Hillel, K., Kaski, P., Korhonen, J., Lenzen, C., Paz, A., & Suomela,
J. (2019). Algebraic methods in the congested clique. Distributed Computing.
Springer Nature. https://doi.org/10.1007/s00446-016-0270-2
chicago: Censor-Hillel, Keren, Petteri Kaski, Janne Korhonen, Christoph Lenzen,
Ami Paz, and Jukka Suomela. “Algebraic Methods in the Congested Clique.” Distributed
Computing. Springer Nature, 2019. https://doi.org/10.1007/s00446-016-0270-2.
ieee: K. Censor-Hillel, P. Kaski, J. Korhonen, C. Lenzen, A. Paz, and J. Suomela,
“Algebraic methods in the congested clique,” Distributed Computing, 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.” Distributed
Computing, vol. 32, no. 6, Springer Nature, 2019, pp. 461–78, doi:10.1007/s00446-016-0270-2.
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'
...