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

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

zbMATH Keywords

data structurelower boundasynchronousdisjoint set unionconcurrentlinearizableunion findwait freeJayanti's wake up

Mathematics Subject Classification ID

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

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)