Optimal Time–Space Tradeoff for Shared Memory Leader Election

DOI10.1006/JAGM.1996.0852MaRDI QIDQ4366876zbMATH OpenOpenAlexFDO

Authors Yehuda Afek, Gideon Stupp

Publication date 7 January 1998

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1996.0852

zbMATH Keywords

complexity hierarchy for multiprocessor synchronization operationsleader election

Mathematics Subject Classification ID

Mathematical problems of computer architecture (68M07) Computer system organization (68M99) Parallel algorithms in computer science (68W10)

Recommendations

• An \(O(1)\) RMRs leader election algorithm
• Time/contention trade-offs for multiprocessor synchronization
• On the space complexity of randomized synchronization
• An \(O(1)\) RMRs leader election algorithm

Cited in

(8)

• Solo-valency and the cost of coordination
• On the space complexity of randomized synchronization
• Proactive Leader Election in Asynchronous Shared Memory Systems
• Constant-Space Localized Byzantine Consensus
• Hundreds of impossibility results for distributed computing
• An \(O(1)\) RMRs leader election algorithm
• An \(O(1)\) RMRs leader election algorithm
• Initializing memory shared by several processors

This page was built for publication: Optimal Time–Space Tradeoff for Shared Memory Leader Election

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