TY - JOUR
T1 - Concurrent disjoint set union
AU - Jayanti, Siddhartha V.
AU - Tarjan, Robert E.
N1 - Funding Information:
This paper is a combination and revision of [] and part of []. Research at Princeton University partially supported by the Princeton University Innovation Fund for Industrial Collaborations and gifts from Microsoft. Part of this work was done at the first AlgoPARC workshop, funded by NSF grant CCF-1745331. The first author is also grateful for funding received through the NDSEG fellowship given by the Department of Defense.
Publisher Copyright:
© 2020, The Author(s).
PY - 2021/12
Y1 - 2021/12
N2 - We develop and analyze concurrent algorithms for the disjoint set union (“union-find”) problem in the shared memory, asynchronous multiprocessor model of computation, with CAS (compare and swap) or DCAS (double compare and swap) as the synchronization primitive. We give a deterministic bounded wait-free algorithm that uses DCAS and has a total work bound of O(m·(log(npm+1)+α(n,mnp))) for a problem with n elements and m operations solved by p processes, where α is a functional inverse of Ackermann’s function. We give two randomized algorithms that use only CAS and have the same work bound in expectation. The analysis of the second randomized algorithm is valid even if the scheduler is adversarial. Our DCAS and randomized algorithms take O(log n) steps per operation, worst-case for the DCAS algorithm, high-probability for the randomized algorithms. Our work and step bounds grow only logarithmically with p, making our algorithms truly scalable. We prove that for a class of symmetric algorithms that includes ours, no better step or work bound is possible. Our work is theoretical, but Alistarh et al (In search of the fastest concurrent union-find algorithm, 2019), Dhulipala et al (A framework for static and incremental parallel graph connectivity algorithms, 2020) and Hong et al (Exploring the design space of static and incremental graph connectivity algorithms on gpus, 2020) have implemented some of our algorithms on CPUs and GPUs and experimented with them. On many realistic data sets, our algorithms run as fast or faster than all others.
AB - We develop and analyze concurrent algorithms for the disjoint set union (“union-find”) problem in the shared memory, asynchronous multiprocessor model of computation, with CAS (compare and swap) or DCAS (double compare and swap) as the synchronization primitive. We give a deterministic bounded wait-free algorithm that uses DCAS and has a total work bound of O(m·(log(npm+1)+α(n,mnp))) for a problem with n elements and m operations solved by p processes, where α is a functional inverse of Ackermann’s function. We give two randomized algorithms that use only CAS and have the same work bound in expectation. The analysis of the second randomized algorithm is valid even if the scheduler is adversarial. Our DCAS and randomized algorithms take O(log n) steps per operation, worst-case for the DCAS algorithm, high-probability for the randomized algorithms. Our work and step bounds grow only logarithmically with p, making our algorithms truly scalable. We prove that for a class of symmetric algorithms that includes ours, no better step or work bound is possible. Our work is theoretical, but Alistarh et al (In search of the fastest concurrent union-find algorithm, 2019), Dhulipala et al (A framework for static and incremental parallel graph connectivity algorithms, 2020) and Hong et al (Exploring the design space of static and incremental graph connectivity algorithms on gpus, 2020) have implemented some of our algorithms on CPUs and GPUs and experimented with them. On many realistic data sets, our algorithms run as fast or faster than all others.
KW - Algorithms
KW - Concurrent
KW - Data structures
KW - Linearizable
KW - Union find
KW - Wait free
UR - http://www.scopus.com/inward/record.url?scp=85119137099&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85119137099&partnerID=8YFLogxK
U2 - 10.1007/s00446-020-00388-x
DO - 10.1007/s00446-020-00388-x
M3 - Article
AN - SCOPUS:85119137099
SN - 0178-2770
VL - 34
SP - 413
EP - 436
JO - Distributed Computing
JF - Distributed Computing
IS - 6
ER -