Randomized Concurrent Set Union and Generalized Wake-Up

DOI10.1145/3293611.3331593OpenAlexW2962741105MaRDI QIDQ5145199FDOQ5145199

Authors Enric Boix-Adserà, S. Jayanti, Robert E. Tarjan 

Publication date 20 January 2021

Published in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3293611.3331593

zbMATH Keywords

data structurelower boundasynchronousdisjoint set unionconcurrentlinearizableunion findwait freeJayanti's wake up

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• A randomized concurrent algorithm for disjoint set union
• An algebraic framework for defining random concurrent behaviours
• Enumeration and random generation of concurrent computations
• scientific article; zbMATH DE number 1304098
• Randomized uniform self-stabilizing mutual exclusion
• Randomized mutual exclusion algorithms revisited
• Concurrent disjoint set union
• The concurrency hierarchy, and algorithms for unbounded concurrency
• Randomized mutual exclusion with sub-logarithmic RMR-complexity

Cited In (3)

• Concurrent disjoint set union
• A wait-free queue with polylogarithmic step complexity
• The amortized analysis of a non-blocking chromatic tree

This page was built for publication: Randomized Concurrent Set Union and Generalized Wake-Up

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145199)