Lower Bounds for Randomized Mutual Exclusion

DOI10.1137/S009753979426513XMaRDI QIDQ4210122zbMATH OpenFDO

Authors Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S009753979426513X

zbMATH Keywords

Markov chainslower boundsmutual exclusionrandomized distributed algorithms

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Distributed algorithms (68W15) Computer system organization (68M99)

Recommendations

• A tight RMR lower bound for randomized mutual exclusion
• An improved lower bound for the time complexity of mutual exclusion
• An improved lower bound for the time complexity of mutual exclusion
• Randomized mutual exclusion with sub-logarithmic RMR-complexity
• Brief announcement, a tight RMR lower bound for randomized mutual exclusion
• Randomized mutual exclusion algorithms revisited
• An \({\Omega}(n\log n)\) lower bound on the cost of mutual exclusion
• Randomized mutual exclusion in \(\mathcal{O}(\log N / \log \log N)\) RMRs
• A time complexity lower bound for adaptive mutual exclusion

Cited in

(10)

• Proving probabilistic correctness statements: the case of Rabin's algorithm for mutual exclusion
• An improved lower bound for the time complexity of mutual exclusion
• Hundreds of impossibility results for distributed computing
• Randomized mutual exclusion with sub-logarithmic RMR-complexity
• Theory of Cryptography
• Shared-memory mutual exclusion: major research trends since 1986
• An \({\Omega}(n\log n)\) lower bound on the cost of mutual exclusion
• Randomized mutual exclusion algorithms revisited
• Bounds on shared memory for mutual exclusion
• Randomized mutual exclusion on a multiple access channel

This page was built for publication: Lower Bounds for Randomized Mutual Exclusion

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