The space complexity of leader election in anonymous networks

DOI10.1142/S0129054110007349MaRDI QIDQ3569285zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(11)

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

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)