The space complexity of leader election in anonymous networks

DOI10.1142/S0129054110007349zbMATH Open1192.68844OpenAlexW2150039590MaRDI QIDQ3569285FDOQ3569285

Authors: Ei Ando, Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita 

Publication date: 18 June 2010

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054110007349

Recommendations

• How much memory is needed for leader election
• How much memory is needed for leader election
• Compact self-stabilizing leader election for general networks
• The Bit Complexity of Randomized Leader Election on a Ring
• Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds

zbMATH Keywords

distributed computingspace complexityanonymous networksleader election problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths

Cited In (11)

• Deterministic geoleader election in disoriented anonymous systems
• Simpler exact leader election via quantum reduction
• How much memory is needed for leader election
• Impact of knowledge on election time in anonymous networks
• How much memory is needed for leader election
• Enumeration and leader election in partially anonymous and multi-hop broadcast networks
• Simplifying Itai-Rodeh leader election for anonymous rings
• Compact self-stabilizing leader election for general networks
• STACS 2005
• Some bounded degree communication networks and optimal leader election
• Election in fully anonymous shared memory systems: tight space bounds and algorithms

This page was built for publication: The space complexity of leader election in anonymous networks

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