A randomized concurrent algorithm for disjoint set union

Siddhartha V. Jayanti, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

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 languageEnglish (US)
Title of host publicationPODC 2016 - Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Pages75-82
Number of pages8
ISBN (Electronic)9781450339643
DOIs
StatePublished - Jul 25 2016
Event35th ACM Symposium on Principles of Distributed Computing, PODC 2016 - Chicago, United States
Duration: Jul 25 2016Jul 28 2016

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing
Volume25-28-July-2016

Other

Other35th ACM Symposium on Principles of Distributed Computing, PODC 2016
CountryUnited States
CityChicago
Period7/25/167/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

    Jayanti, S. V., & Tarjan, R. E. (2016). A randomized concurrent algorithm for disjoint set union. In 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