---
_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'
...