A Randomized Concurrent Algorithm for Disjoint Set Union
Siddhartha Jayanti, Robert Endre Tarjan · 2016
Disjoint set union is a basic problem in data structures with a wide variety of applications. We extend a known efficient sequential algorithm for this problem to obtain a simple and efficient concurrent wait-free algorithm running on an asynchronous parallel random access machine (APRAM). Crucial to our result is the use of randomization. Under a certain independence assumption, for a problem instance in which there are n elements, m operations, and l processes, our algorithm does θ(m (α{n, m/nl) + log (nl/m + 1 ))) expected work, where the expectation is over the random choices made by the algorithm and α is a functional inverse of Ackermann's function. In addition, each operation takes O(log n) steps with high probability.