---
_id: '10853'
abstract:
- lang: eng
  text: Dynamic Connectivity is a fundamental algorithmic graph problem, motivated
    by a wide range of applications to social and communication networks and used
    as a building block in various other algorithms, such as the bi-connectivity and
    the dynamic minimal spanning tree problems. In brief, we wish to maintain the
    connected components of the graph under dynamic edge insertions and deletions.
    In the sequential case, the problem has been well-studied from both theoretical
    and practical perspectives. However, much less is known about efficient concurrent
    solutions to this problem. This is the gap we address in this paper. We start
    from one of the classic data structures used to solve this problem, the Euler
    Tour Tree. Our first contribution is a non-blocking single-writer implementation
    of it. We leverage this data structure to obtain the first truly concurrent generalization
    of dynamic connectivity, which preserves the time complexity of its sequential
    counterpart, but is also scalable in practice. To achieve this, we rely on three
    main techniques. The first is to ensure that connectivity queries, which usually
    dominate real-world workloads, are non-blocking. The second non-trivial technique
    expands the above idea by making all queries that do not change the connectivity
    structure non-blocking. The third ingredient is applying fine-grained locking
    for updating the connected components, which allows operations on disjoint components
    to occur in parallel. We evaluate the resulting algorithm on various workloads,
    executing on both real and synthetic graphs. The results show the efficiency of
    each of the proposed optimizations; the most efficient variant improves the performance
    of a coarse-grained based implementation on realistic scenarios up to 6x on average
    and up to 30x when connectivity queries dominate.
article_processing_charge: No
arxiv: 1
author:
- first_name: Alexander
  full_name: Fedorov, Alexander
  last_name: Fedorov
- first_name: Nikita
  full_name: Koval, Nikita
  last_name: Koval
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
citation:
  ama: 'Fedorov A, Koval N, Alistarh D-A. A scalable concurrent algorithm for dynamic
    connectivity. In: <i>Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms
    and Architectures</i>. Association for Computing Machinery; 2021:208-220. doi:<a
    href="https://doi.org/10.1145/3409964.3461810">10.1145/3409964.3461810</a>'
  apa: 'Fedorov, A., Koval, N., &#38; Alistarh, D.-A. (2021). A scalable concurrent
    algorithm for dynamic connectivity. In <i>Proceedings of the 33rd ACM Symposium
    on Parallelism in Algorithms and Architectures</i> (pp. 208–220). Virtual, Online:
    Association for Computing Machinery. <a href="https://doi.org/10.1145/3409964.3461810">https://doi.org/10.1145/3409964.3461810</a>'
  chicago: Fedorov, Alexander, Nikita Koval, and Dan-Adrian Alistarh. “A Scalable
    Concurrent Algorithm for Dynamic Connectivity.” In <i>Proceedings of the 33rd
    ACM Symposium on Parallelism in Algorithms and Architectures</i>, 208–20. Association
    for Computing Machinery, 2021. <a href="https://doi.org/10.1145/3409964.3461810">https://doi.org/10.1145/3409964.3461810</a>.
  ieee: A. Fedorov, N. Koval, and D.-A. Alistarh, “A scalable concurrent algorithm
    for dynamic connectivity,” in <i>Proceedings of the 33rd ACM Symposium on Parallelism
    in Algorithms and Architectures</i>, Virtual, Online, 2021, pp. 208–220.
  ista: 'Fedorov A, Koval N, Alistarh D-A. 2021. A scalable concurrent algorithm for
    dynamic connectivity. Proceedings of the 33rd ACM Symposium on Parallelism in
    Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and
    Architectures, 208–220.'
  mla: Fedorov, Alexander, et al. “A Scalable Concurrent Algorithm for Dynamic Connectivity.”
    <i>Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures</i>,
    Association for Computing Machinery, 2021, pp. 208–20, doi:<a href="https://doi.org/10.1145/3409964.3461810">10.1145/3409964.3461810</a>.
  short: A. Fedorov, N. Koval, D.-A. Alistarh, in:, Proceedings of the 33rd ACM Symposium
    on Parallelism in Algorithms and Architectures, Association for Computing Machinery,
    2021, pp. 208–220.
conference:
  end_date: 2021-07-08
  location: Virtual, Online
  name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures'
  start_date: 2021-07-06
date_created: 2022-03-18T08:21:47Z
date_published: 2021-07-01T00:00:00Z
date_updated: 2022-03-18T08:45:46Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3409964.3461810
external_id:
  arxiv:
  - '2105.08098'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2105.08098
month: '07'
oa: 1
oa_version: Preprint
page: 208-220
publication: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and
  Architectures
publication_identifier:
  isbn:
  - '9781450380706'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: A scalable concurrent algorithm for dynamic connectivity
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '9678'
abstract:
- lang: eng
  text: We introduce a new graph problem, the token dropping game, and we show how
    to solve it efficiently in a distributed setting. We use the token dropping game
    as a tool to design an efficient distributed algorithm for stable orientations
    and more generally for locally optimal semi-matchings. The prior work by Czygrinow
    et al. (DISC 2012) finds a stable orientation in O(Δ^5) rounds in graphs of maximum
    degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ).
    For the more general problem of locally optimal semi-matchings, the prior upper
    bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement
    for C = o(S); here C and S are the maximum degrees of customers and servers, respectively.
acknowledgement: We thank Orr Fischer, Juho Hirvonen, and Tuomo Lempiäinen for valuable
  discussions. This project has received funding from the European Union’s Horizon
  2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
  No. 840605.
article_processing_charge: No
arxiv: 1
author:
- first_name: Sebastian
  full_name: Brandt, Sebastian
  last_name: Brandt
- first_name: Barbara
  full_name: Keller, Barbara
  last_name: Keller
- first_name: Joel
  full_name: Rybicki, Joel
  id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
  last_name: Rybicki
  orcid: 0000-0002-6432-6646
- first_name: Jukka
  full_name: Suomela, Jukka
  last_name: Suomela
- first_name: Jara
  full_name: Uitto, Jara
  last_name: Uitto
citation:
  ama: 'Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. Efficient load-balancing
    through distributed token dropping. In: <i>Annual ACM Symposium on Parallelism
    in Algorithms and Architectures</i>. ; 2021:129-139. doi:<a href="https://doi.org/10.1145/3409964.3461785">10.1145/3409964.3461785</a>'
  apa: Brandt, S., Keller, B., Rybicki, J., Suomela, J., &#38; Uitto, J. (2021). Efficient
    load-balancing through distributed token dropping. In <i>Annual ACM Symposium
    on Parallelism in Algorithms and Architectures</i> (pp. 129–139).  Virtual Event,
    United States. <a href="https://doi.org/10.1145/3409964.3461785">https://doi.org/10.1145/3409964.3461785</a>
  chicago: Brandt, Sebastian, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara
    Uitto. “Efficient Load-Balancing through Distributed Token Dropping.” In <i>Annual
    ACM Symposium on Parallelism in Algorithms and Architectures</i>, 129–39, 2021.
    <a href="https://doi.org/10.1145/3409964.3461785">https://doi.org/10.1145/3409964.3461785</a>.
  ieee: S. Brandt, B. Keller, J. Rybicki, J. Suomela, and J. Uitto, “Efficient load-balancing
    through distributed token dropping,” in <i>Annual ACM Symposium on Parallelism
    in Algorithms and Architectures</i>,  Virtual Event, United States, 2021, pp.
    129–139.
  ista: 'Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. 2021. Efficient load-balancing
    through distributed token dropping. Annual ACM Symposium on Parallelism in Algorithms
    and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures
    , 129–139.'
  mla: Brandt, Sebastian, et al. “Efficient Load-Balancing through Distributed Token
    Dropping.” <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i>,
    2021, pp. 129–39, doi:<a href="https://doi.org/10.1145/3409964.3461785">10.1145/3409964.3461785</a>.
  short: S. Brandt, B. Keller, J. Rybicki, J. Suomela, J. Uitto, in:, Annual ACM Symposium
    on Parallelism in Algorithms and Architectures, 2021, pp. 129–139.
conference:
  end_date: 2021-07-08
  location: ' Virtual Event, United States'
  name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures '
  start_date: 2021-07-06
date_created: 2021-07-18T22:01:22Z
date_published: 2021-07-06T00:00:00Z
date_updated: 2025-04-14T07:50:55Z
day: '06'
department:
- _id: DaAl
doi: 10.1145/3409964.3461785
ec_funded: 1
external_id:
  arxiv:
  - '2005.07761'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2005.07761
month: '07'
oa: 1
oa_version: Preprint
page: 129-139
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '840605'
  name: Coordination in constrained and natural distributed systems
publication: Annual ACM Symposium on Parallelism in Algorithms and Architectures
publication_identifier:
  isbn:
  - '9781450380706'
publication_status: published
quality_controlled: '1'
related_material:
  record:
  - id: '15074'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Efficient load-balancing through distributed token dropping
type: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
year: '2021'
...