@inproceedings{95575cc60dbf461c9aea57ea9b6c878a,

title = "Randomized concurrent set union and generalized wake-up",

abstract = "We consider the disjoint set union problem in the asynchronous shared memory multiprocessor computation model. We design a randomized algorithm that performs at most O(log n) work per operation (with high probability), and performs at most O(m #8226; (α(n, m/(np)) + log(np/m + 1)) total work in expectation for a problem instance with m operations on n elements solved by p processes. Our algorithm is the first to have work bounds that grow sublinearly with p against an adversarial scheduler. We use Jayanti's Wake Up problem and our newly defined Generalized Wake Up problem to prove several lower bounds on concurrent set union. We show an (log min {n,p}) expected work lower bound on the cost of any single operation on a set union algorithm. This shows that our single-operation upper bound is optimal across all algorithms when p = n(1). Furthermore, we identify a class of {"}symmetric algorithms'' that captures the complexities of all the known algorithms for the disjoint set union problem, and prove an (m(α(n, m(np)) + log(np/m + 1))) expected total work lower bound on algorithms of this class, thereby showing that our algorithm has optimal total work complexity for this class. Finally, we prove that any randomized algorithm, symmetric or not, cannot breach an (m (α(n, m/n) + log log(np/m + 1))) expected total work lower bound.",

keywords = "Asynchronous, Concurrent, Data structure, Disjoint set union, Jayanti's wake up, Linearizable, Lower bound, Union find, Wait free",

author = "Siddhartha Jayanti and Tarjan, {Robert E.} and Enric Boix-Adser",

note = "Publisher Copyright: {\textcopyright} 2019 ACM.; 38th ACM Symposium on Principles of Distributed Computing, PODC 2019 ; Conference date: 29-07-2019 Through 02-08-2019",

year = "2019",

month = jul,

day = "16",

doi = "10.1145/3293611.3331593",

language = "English (US)",

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

publisher = "Association for Computing Machinery",

pages = "187--196",

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

}