@inproceedings{13262,
  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.},
  author       = {Fedorov, Alexander and Hashemi, Diba and Nadiradze, Giorgi and Alistarh, Dan-Adrian},
  booktitle    = {Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures},
  isbn         = {9781450395458},
  location     = {Orlando, FL, United States},
  pages        = {261--271},
  publisher    = {Association for Computing Machinery},
  title        = {{Provably-efficient and internally-deterministic parallel Union-Find}},
  doi          = {10.1145/3558481.3591082},
  year         = {2023},
}