Randomized mutual exclusion algorithms revisited

DOI10.1145/135419.135468MaRDI QIDQ5348858zbMATH OpenOpenAlexFDO

Authors Eyal Kushilevitz, Michael O. Rabin

Publication date 21 August 2017

Published in Proceedings of the eleventh annual ACM symposium on Principles of distributed computing - PODC '92 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Distributed algorithms (68W15)

Recommendations

• Lower Bounds for Randomized Mutual Exclusion
• RMR-efficient randomized abortable mutual exclusion (extended abstract)
• Randomized mutual exclusion in \(\mathcal{O}(\log N / \log \log N)\) RMRs
• Adaptive randomized mutual exclusion in sub-logarithmic expected time
• Randomized mutual exclusion with sub-logarithmic RMR-complexity

Cited in

(19)

• Proving probabilistic correctness statements: the case of Rabin's algorithm for mutual exclusion
• Layered reasoning for randomized distributed algorithms
• Latticed \(k\)-induction with an application to probabilistic programs
• Fast and fair randomized wait-free locks
• Randomized mutual exclusion with sub-logarithmic RMR-complexity
• Compositional verification of randomized distributed algorithms
• Analysis of timing-based mutual exclusion with random times
• Randomized Concurrent Set Union and Generalized Wake-Up
• Using probabilistic Kleene algebra pKA for protocol verification
• Shared-memory mutual exclusion: major research trends since 1986
• Nondominated \(k\)-coteries for multiple mutual exclusion
• Randomized dining philosophers without fairness assumption
• Randomized distributed access to mutually exclusive resources
• Lower Bounds for Randomized Mutual Exclusion
• Structural transformations for data-enriched real-time systems
• A closer look at fault tolerance
• Probabilistic guarded commands mechanized in HOL
• Randomized mutual exclusion on a multiple access channel
• Randomized leader election

This page was built for publication: Randomized mutual exclusion algorithms revisited

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