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

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

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

Publisher | Association for Computing Machinery |

Pages | 75-82 |

Number of pages | 8 |

ISBN (Electronic) | 9781450339643 |

DOIs | |

State | Published - Jul 25 2016 |

Event | 35th ACM Symposium on Principles of Distributed Computing, PODC 2016 - Chicago, United States Duration: Jul 25 2016 → Jul 28 2016 |

### Publication series

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

Volume | 25-28-July-2016 |

### Other

Other | 35th ACM Symposium on Principles of Distributed Computing, PODC 2016 |
---|---|

Country | United States |

City | Chicago |

Period | 7/25/16 → 7/28/16 |

### All Science Journal Classification (ASJC) codes

- Software
- Hardware and Architecture
- Computer Networks and Communications

### Keywords

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

## Fingerprint Dive into the research topics of 'A randomized concurrent algorithm for disjoint set union'. Together they form a unique fingerprint.

## Cite this

*PODC 2016 - Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing*(pp. 75-82). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; Vol. 25-28-July-2016). Association for Computing Machinery. https://doi.org/10.1145/2933057.2933108