A randomized concurrent algorithm for disjoint set union

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 asyn- chronous parallel random access machine (APRAM). Cru- cial 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 algo- rithm does (equition presented) 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. We point out some gaps in the earlier work on this prob- lem by Anderson and Woll [1]. More importantly, our algo- rithm is significantly simpler than theirs. Finally, under our independence assumption our algorithm achieves speedup close to linear for applications in which all or most of the processes can be kept busy, thereby partially answering an open problem posed by them.