The complexity of leader election in diameter-two networks

DOI10.1007/s00446-019-00354-2zbMath1434.68047OpenAlexW2946052740MaRDI QIDQ1988528

Gopal Pandurangan, Peter Robinson, Soumyottam Chatterjee

Publication date: 23 April 2020

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-019-00354-2

zbMATH Keywords

randomized algorithmlower boundtime complexitydistributed algorithmleader electionmessage complexity

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (1)

Improved deterministic leader election in diameter-two networks

Cites Work

• Unnamed Item
• Unnamed Item
• Sublinear bounds for randomized leader election
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks
• The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
• Distributed Computing: A Locality-Sensitive Approach
• Leader Election in Well-Connected Graphs
• Brief Announcement
• On the Complexity of Universal Leader Election
• Efficient distributed approximation algorithms via probabilistic tree embeddings

This page was built for publication: The complexity of leader election in diameter-two networks