research-article

A Randomized Concurrent Algorithm for Disjoint Set Union

Authors:

Siddhartha V. Jayanti,

Robert E. TarjanAuthors Info & Claims

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

Pages 75 - 82

https://doi.org/10.1145/2933057.2933108

Published: 25 July 2016 Publication History

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 asynchronous parallel random access machine (APRAM). Crucial 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 algorithm does θ(m (α{n, m/nl) + log (nl/m + 1 ))) 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 problem by Anderson and Woll [1]. More importantly, our algorithm 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.

References

[1]

R. J. Anderson and H. S. Woll. Wait-free parallel algorithms for the union-find problem. In Full version of STOC '91: Proceedings of the 23rd ACM Symposium on Theory of Computation. Unpublished Manuscript, 1994.

Digital Library

[2]

V. Bloemen. On-The-Fly Parallel Decomposition of Strongly Connected Components. Master's thesis, University of Twente, 2015.

[3]

V. Bloemen, A. Laarman, and J. van de Pol. Multi-core on-the-fly scc decomposition. In Proceedings of the 21st ACM SIGPLAN symposium on Principles and practice of parallel programming, PPoPP '16, page to appear, 2016.

Digital Library

[4]

F. Chung and L. Lu. Concentration Inequalities and Martingale Inequalities: A Survey, pages 79--127. 2005.

[5]

R. Cole and O. Zajicek. The apram: Incorporating asynchrony into the pram model. In Proceedings of the First Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '89, pages 169--178, New York, NY, USA, 1989. ACM.

Digital Library

[6]

W. Feller. An Introduction to Probability Theory and Its Applications, volume 1. Wiley, January 1968.

[7]

W. Fraczak, L. Georgiadis, A. Miller, and R. E. Tarjan. Corrections to "finding dominators via disjoint set union" {J. discrete algorithms 23 (2013) 2--20}. J. Discrete Algorithms, 26:106--110, 2014.

Digital Library

[8]

M. L. Fredman and M. E. Saks. The cell probe complexity of dynamic data structures. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14--17, 1989, Seattle, Washigton, USA, pages 345--354, 1989.

Digital Library

[9]

P. B. Gibbons. A more practical pram model. In Proceedings of the First Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '89, pages 158--168, New York, NY, USA, 1989. ACM.

Digital Library

[10]

A. Goel, S. Khanna, D. H. Larkin, and R. E. Tarjan. Disjoint set union with randomized linking. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1005--1017, 2014.

Digital Library

[11]

M. Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124--149, Jan. 1991.

Digital Library

[12]

M. Herlihy and J. M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463--492, Jul 1990.

Digital Library

[13]

S. V. Jayanti and R. E. Tarjan. An efficient deterministic concurrent algorithm for disjoint set union. In To Appear.

[14]

C. Lattner and V. Adve. Automatic pool allocation for disjoint data structures. SIGPLAN Not., 38(2 supplement):13--24, June 2002.

Digital Library

[15]

F. Manne and M. M. A. Patwary. A scalable parallel union-find algorithm for distributed memory computers. In Proceedings of the 8th International Conference on Parallel Processing and Applied Mathematics: Part I, PPAM'09, pages 186--195, Berlin, Heidelberg, 2010. Springer-Verlag.

Digital Library

[16]

R. Sedgewick and K. Wayne. Algorithms, 4th Edition. Addison-Wesley, 2011.

Digital Library

[17]

R. E. Tarjan. Efficiency of a good but not linear set union algorithm. J. ACM, 22(2):215--225, Apr. 1975.

Digital Library

[18]

R. E. Tarjan and J. van Leeuwen. Worst-case analysis of set union algorithms. J. ACM, 31(2):245--281, Mar. 1984.

Digital Library

[19]

P. Wolper. Lectures on formal methods and performance analysis. chapter Constructing Automata from Temporal Logic Formulas: A Tutorial, pages 261--277. Springer-Verlag New York, Inc., New York, NY, USA, 2002.

Digital Library

Cited By

Jayanti STarjan RDhulipala LSun Y(2024)Fast, Scalable, and Machine-Verified Multicore Disjoint Set Union Data Structures and their Wide Deployment in Parallel Algorithms (Abstract)Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing10.1145/3670684.3673405(27-28)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3670684.3673405
Jayanti PJayanti SYavuz UHernandez L(2024)A Universal, Sound, and Complete Forward Reasoning Technique for Machine-Verified Proofs of LinearizabilityProceedings of the ACM on Programming Languages10.1145/36329248:POPL(2456-2484)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632924
Keramatian AGulisano VPapatriantafilou MTsigas P(2023)PARMA-CC: A family of parallel multiphase approximate cluster combining algorithmsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2023.02.001177(68-88)Online publication date: Jul-2023
https://doi.org/10.1016/j.jpdc.2023.02.001
Show More Cited By

Index Terms

A Randomized Concurrent Algorithm for Disjoint Set Union
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Randomized Concurrent Set Union and Generalized Wake-Up
PODC '19: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing

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; (α(...
Concurrent disjoint set union
Abstract
We develop and analyze concurrent algorithms for the disjoint set union (“union-find” ) problem in the shared memory, asynchronous multiprocessor model of computation, with CAS (compare and swap) or DCAS (double compare and swap) as the ... $((\frac{}{}) (\frac{}{}))$
Melding priority queues

We show that any priority queue data structure that supports insert, delete, and find-min operations in pq(n) amortized time, where n is an upper bound on the number of elements in the priority queue, can be converted into a priority queue data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

July 2016

508 pages

ISBN:9781450339643

DOI:10.1145/2933057

General Chair:
George Giakkoupis
INRIA, France

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '16

Sponsor:

PODC '16: ACM Symposium on Principles of Distributed Computing

July 25 - 28, 2016

Illinois, Chicago, USA

Acceptance Rates

PODC '16 Paper Acceptance Rate 40 of 149 submissions, 27%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
706
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)14

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jayanti STarjan RDhulipala LSun Y(2024)Fast, Scalable, and Machine-Verified Multicore Disjoint Set Union Data Structures and their Wide Deployment in Parallel Algorithms (Abstract)Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing10.1145/3670684.3673405(27-28)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3670684.3673405
Jayanti PJayanti SYavuz UHernandez L(2024)A Universal, Sound, and Complete Forward Reasoning Technique for Machine-Verified Proofs of LinearizabilityProceedings of the ACM on Programming Languages10.1145/36329248:POPL(2456-2484)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632924
Keramatian AGulisano VPapatriantafilou MTsigas P(2023)PARMA-CC: A family of parallel multiphase approximate cluster combining algorithmsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2023.02.001177(68-88)Online publication date: Jul-2023
https://doi.org/10.1016/j.jpdc.2023.02.001
Liu XLumsdaine AHalappanavar MBarker KGebremedhin A(2022)Direction-optimizing Label Propagation Framework for Structure Detection in Graphs: Design, Implementation, and Experimental AnalysisACM Journal of Experimental Algorithmics10.1145/356459327(1-31)Online publication date: 13-Dec-2022
https://dl.acm.org/doi/10.1145/3564593
Liu STarjan R(2022)Simple Concurrent Connected Components AlgorithmsACM Transactions on Parallel Computing10.1145/35435469:2(1-26)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1145/3543546
Blin NCarlinet ELemaitre FLacassagne LGeraud T(2022)Max-Tree Computation on GPUsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.315848833:12(3520-3531)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TPDS.2022.3158488
Keramatian AGulisano VPapatriantafilou MTsigas P(2022): Integrated Parallel Density-Based Clustering Through Locality-Sensitive HashingEuro-Par 2022: Parallel Processing10.1007/978-3-031-12597-3_17(268-284)Online publication date: 22-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-12597-3_17
Dhulipala LHong CShun J(2021)ConnectItProceedings of the VLDB Endowment10.14778/3436905.343692314:4(653-667)Online publication date: 22-Feb-2021
https://dl.acm.org/doi/10.14778/3436905.3436923
Yadav AShokeen HYadav J(2021)Disjoint Set Union for Trees2021 12th International Conference on Computing Communication and Networking Technologies (ICCCNT)10.1109/ICCCNT51525.2021.9580066(1-6)Online publication date: 6-Jul-2021
https://doi.org/10.1109/ICCCNT51525.2021.9580066
Koohi Esfahani MKilpatrick PVandierendonck H(2021)Thrifty Label Propagation: Fast Connected Components for Skewed-Degree Graphs2021 IEEE International Conference on Cluster Computing (CLUSTER)10.1109/Cluster48925.2021.00042(226-237)Online publication date: Sep-2021
https://doi.org/10.1109/Cluster48925.2021.00042
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents