  The disjoint set union problem 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 p processes, our algorithm does Theta(m (alpha(n, m/(np)) + log(np/m + 1)))
expected work, where the expectation is over the random choices made by the
algorithm and alpha is a functional inverse of Ackermann's function. In
addition, each operation takes O(log n) steps with high probability. Our
algorithm is significantly simpler and more efficient than previous algorithms
proposed by Anderson and Woll. Under our independence assumption, our algorithm
achieves almost-linear speed-up for applications in which all or most of the
processes can be kept busy.
