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.|
|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|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.