### 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.

Original language | English (US) |
---|---|

Title of host publication | PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing |

Publisher | Association for Computing Machinery |

Pages | 187-196 |

Number of pages | 10 |

ISBN (Electronic) | 9781450362177 |

DOIs | |

State | Published - Jul 16 2019 |

Event | 38th ACM Symposium on Principles of Distributed Computing, PODC 2019 - Toronto, Canada Duration: Jul 29 2019 → Aug 2 2019 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Principles of Distributed Computing |
---|

### Conference

Conference | 38th ACM Symposium on Principles of Distributed Computing, PODC 2019 |
---|---|

Country | Canada |

City | Toronto |

Period | 7/29/19 → 8/2/19 |

### All Science Journal Classification (ASJC) codes

- Software
- Hardware and Architecture
- Computer Networks and Communications

### Keywords

- Asynchronous
- Concurrent
- Data structure
- Disjoint set union
- Jayanti's wake up
- Linearizable
- Lower bound
- Union find
- Wait free

## Fingerprint Dive into the research topics of 'Randomized concurrent set union and generalized wake-up'. Together they form a unique fingerprint.

## Cite this

*PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing*(pp. 187-196). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing). Association for Computing Machinery. https://doi.org/10.1145/3293611.3331593