Randomized concurrent set union and generalized wake-up

Siddhartha Jayanti, Robert E. Tarjan, Enric Boix-Adser

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

2 Scopus citations

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 languageEnglish (US)
Title of host publicationPODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Pages187-196
Number of pages10
ISBN (Electronic)9781450362177
DOIs
StatePublished - Jul 16 2019
Event38th ACM Symposium on Principles of Distributed Computing, PODC 2019 - Toronto, Canada
Duration: Jul 29 2019Aug 2 2019

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

Conference38th ACM Symposium on Principles of Distributed Computing, PODC 2019
CountryCanada
CityToronto
Period7/29/198/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

    Jayanti, S., Tarjan, R. E., & Boix-Adser, E. (2019). Randomized concurrent set union and generalized wake-up. In 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