---
res:
  bibo_abstract:
  - '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.@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Alexander
      foaf_name: Fedorov, Alexander
      foaf_surname: Fedorov
      foaf_workInfoHomepage: http://www.librecat.org/personId=2e711909-896a-11ed-bdf8-eb0f5a2984c6
  - foaf_Person:
      foaf_givenName: Diba
      foaf_name: Hashemi, Diba
      foaf_surname: Hashemi
      foaf_workInfoHomepage: http://www.librecat.org/personId=ed9595ea-2f8f-11ee-ba95-d2b546540783
  - foaf_Person:
      foaf_givenName: Giorgi
      foaf_name: Nadiradze, Giorgi
      foaf_surname: Nadiradze
      foaf_workInfoHomepage: http://www.librecat.org/personId=3279A00C-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0001-5634-0731
  - foaf_Person:
      foaf_givenName: Dan-Adrian
      foaf_name: Alistarh, Dan-Adrian
      foaf_surname: Alistarh
      foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0003-3650-940X
  bibo_doi: 10.1145/3558481.3591082
  dct_date: 2023^xs_gYear
  dct_identifier:
  - UT:001108889000024
  dct_isPartOf:
  - http://id.crossref.org/issn/9781450395458
  dct_language: eng
  dct_publisher: Association for Computing Machinery@
  dct_title: Provably-efficient and internally-deterministic parallel Union-Find@
...