@inproceedings{815ef26168434567b33a35dcbd5a7e96,

title = "A randomized concurrent algorithm for disjoint set union",

abstract = "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.",

keywords = "Algorithms, Concurrent, Data structures, Disjoint set union, Graph algorithms, Linearizable, Multiprocessor, Par-allel, Randomized, Set union, Union-find, Wait-free",

author = "Jayanti, {Siddhartha V.} and Tarjan, {Robert E.}",

note = "Publisher Copyright: {\textcopyright} 2016 ACM. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.; 35th ACM Symposium on Principles of Distributed Computing, PODC 2016 ; Conference date: 25-07-2016 Through 28-07-2016",

year = "2016",

month = jul,

day = "25",

doi = "10.1145/2933057.2933108",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Association for Computing Machinery",

pages = "75--82",

booktitle = "PODC 2016 - Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing",

}