Skip to main content

A Randomized Concurrent Algorithm for Disjoint Set Union

Author(s): Jayanti, Siddhartha V; Tarjan, Robert E

To refer to this page use:
Abstract: 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.
Publication Date: 2016
Citation: Jayanti, Siddhartha V, Tarjan, Robert E. (A Randomized Concurrent Algorithm for Disjoint Set Union
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.