---
_id: '13262'
abstract:
- lang: eng
  text: 'Determining the degree of inherent parallelism in classical sequential algorithms
    and leveraging it for fast parallel execution is a key topic in parallel computing,
    and detailed analyses are known for a wide range of classical algorithms. In this
    paper, we perform the first such analysis for the fundamental Union-Find problem,
    in which we are given a graph as a sequence of edges, and must maintain its connectivity
    structure under edge additions. We prove that classic sequential algorithms for
    this problem are well-parallelizable under reasonable assumptions, addressing
    a conjecture by [Blelloch, 2017]. More precisely, we show via a new potential
    argument that, under uniform random edge ordering, parallel union-find operations
    are unlikely to interfere: T concurrent threads processing the graph in parallel
    will encounter memory contention O(T2 · log |V| · log |E|) times in expectation,
    where |E| and |V| are the number of edges and nodes in the graph, respectively.
    We leverage this result to design a new parallel Union-Find algorithm that is
    both internally deterministic, i.e., its results are guaranteed to match those
    of a sequential execution, but also work-efficient and scalable, as long as the
    number of threads T is O(|E|1 over 3 - ε), for an arbitrarily small constant ε
    > 0, which holds for most large real-world graphs. We present lower bounds which
    show that our analysis is close to optimal, and experimental results suggesting
    that the performance cost of internal determinism is limited.'
article_processing_charge: Yes (in subscription journal)
arxiv: 1
author:
- first_name: Alexander
  full_name: Fedorov, Alexander
  id: 2e711909-896a-11ed-bdf8-eb0f5a2984c6
  last_name: Fedorov
- first_name: Diba
  full_name: Hashemi, Diba
  id: ed9595ea-2f8f-11ee-ba95-d2b546540783
  last_name: Hashemi
- first_name: Giorgi
  full_name: Nadiradze, Giorgi
  id: 3279A00C-F248-11E8-B48F-1D18A9856A87
  last_name: Nadiradze
- 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, Hashemi D, Nadiradze G, Alistarh D-A. Provably-efficient and internally-deterministic
    parallel Union-Find. In: <i>Proceedings of the 35th ACM Symposium on Parallelism
    in Algorithms and Architectures</i>. Association for Computing Machinery; 2023:261-271.
    doi:<a href="https://doi.org/10.1145/3558481.3591082">10.1145/3558481.3591082</a>'
  apa: 'Fedorov, A., Hashemi, D., Nadiradze, G., &#38; Alistarh, D.-A. (2023). Provably-efficient
    and internally-deterministic parallel Union-Find. In <i>Proceedings of the 35th
    ACM Symposium on Parallelism in Algorithms and Architectures</i> (pp. 261–271).
    Orlando, FL, United States: Association for Computing Machinery. <a href="https://doi.org/10.1145/3558481.3591082">https://doi.org/10.1145/3558481.3591082</a>'
  chicago: Fedorov, Alexander, Diba Hashemi, Giorgi Nadiradze, and Dan-Adrian Alistarh.
    “Provably-Efficient and Internally-Deterministic Parallel Union-Find.” In <i>Proceedings
    of the 35th ACM Symposium on Parallelism in Algorithms and Architectures</i>,
    261–71. Association for Computing Machinery, 2023. <a href="https://doi.org/10.1145/3558481.3591082">https://doi.org/10.1145/3558481.3591082</a>.
  ieee: A. Fedorov, D. Hashemi, G. Nadiradze, and D.-A. Alistarh, “Provably-efficient
    and internally-deterministic parallel Union-Find,” in <i>Proceedings of the 35th
    ACM Symposium on Parallelism in Algorithms and Architectures</i>, Orlando, FL,
    United States, 2023, pp. 261–271.
  ista: 'Fedorov A, Hashemi D, Nadiradze G, Alistarh D-A. 2023. Provably-efficient
    and internally-deterministic parallel Union-Find. Proceedings of the 35th ACM
    Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism
    in Algorithms and Architectures, 261–271.'
  mla: Fedorov, Alexander, et al. “Provably-Efficient and Internally-Deterministic
    Parallel Union-Find.” <i>Proceedings of the 35th ACM Symposium on Parallelism
    in Algorithms and Architectures</i>, Association for Computing Machinery, 2023,
    pp. 261–71, doi:<a href="https://doi.org/10.1145/3558481.3591082">10.1145/3558481.3591082</a>.
  short: A. Fedorov, D. Hashemi, G. Nadiradze, D.-A. Alistarh, in:, Proceedings of
    the 35th ACM Symposium on Parallelism in Algorithms and Architectures, Association
    for Computing Machinery, 2023, pp. 261–271.
conference:
  end_date: 2023-06-19
  location: Orlando, FL, United States
  name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures'
  start_date: 2023-06-17
date_created: 2023-07-23T22:01:12Z
date_published: 2023-06-17T00:00:00Z
date_updated: 2023-07-31T10:54:32Z
day: '17'
ddc:
- '000'
department:
- _id: DaAl
- _id: GradSch
doi: 10.1145/3558481.3591082
external_id:
  arxiv:
  - '2304.09331'
file:
- access_level: open_access
  checksum: 72e312aabf0c5248c99b5cd3a88e4c88
  content_type: application/pdf
  creator: dernst
  date_created: 2023-07-31T10:53:08Z
  date_updated: 2023-07-31T10:53:08Z
  file_id: '13334'
  file_name: 2023_SPAA_Fedorov.pdf
  file_size: 2087937
  relation: main_file
  success: 1
file_date_updated: 2023-07-31T10:53:08Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 261-271
publication: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and
  Architectures
publication_identifier:
  isbn:
  - '9781450395458'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Provably-efficient and internally-deterministic parallel Union-Find
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...