Provably-efficient and internally-deterministic parallel Union-Find Fedorov, Alexander Hashemi, Diba Nadiradze, Giorgi ; https://orcid.org/0000-0001-5634-0731 Alistarh, Dan-Adrian ; https://orcid.org/0000-0003-3650-940X ddc:000 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. Association for Computing Machinery 2023 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/13262 https://research-explorer.ista.ac.at/download/13262/13334 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> eng info:eu-repo/semantics/altIdentifier/doi/10.1145/3558481.3591082 info:eu-repo/semantics/altIdentifier/isbn/9781450395458 info:eu-repo/semantics/altIdentifier/wos/001108889000024 info:eu-repo/semantics/altIdentifier/arxiv/2304.09331 https://creativecommons.org/licenses/by/4.0/ info:eu-repo/semantics/openAccess