Lower Bounds for Randomized Mutual Exclusion

DOI10.1137/S009753979426513XzbMATH Open0907.68100MaRDI QIDQ4210122FDOQ4210122

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)

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

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)

Cited In (6)

• Hundreds of impossibility results for distributed computing
• An improved lower bound for the time complexity of mutual exclusion
• Randomized mutual exclusion with sub-logarithmic RMR-complexity
• Theory of Cryptography
• Shared-memory mutual exclusion: major research trends since 1986
• Bounds on shared memory for mutual exclusion

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)