On the complexity of universal leader election

DOI10.1145/2484239.2484274MaRDI QIDQ5176087zbMATH OpenOpenAlexFDO

Authors Shay Kutten, Gopal Pandurangan, Peter Robinson, Amitabh Trehan, David Peleg

Publication date 2 March 2015

Published in Proceedings of the 2013 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://pureadmin.qub.ac.uk/ws/files/17451767/Pure_Jacm_Version.pdf

zbMATH Keywords

distributed algorithmleader electionlower bound

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20)

Recommendations

• On the Complexity of Universal Leader Election
• The complexity of leader election in diameter-two networks
• Leader election in well-connected graphs

Cited in

(12)

• Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds
• Randomized leader election
• The complexity of leader election in diameter-two networks
• Leader election in well-connected graphs
• Beeping a deterministic time-optimal leader election
• Leader election in well-connected graphs
• Sublinear message bounds for randomized agreement
• On the Complexity of Universal Leader Election
• Communication costs in a geometric communication network
• Improved deterministic leader election in diameter-two networks
• Smoothed Analysis of Leader Election in Distributed Networks
• Singularly optimal randomized leader election

This page was built for publication: On the complexity of universal leader election

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