Leader election in well-connected graphs

DOI10.1007/s00453-022-01068-xOpenAlexW2950831784MaRDI QIDQ2696279

Peter Robinson, Seth Gilbert, Suman Sourav

Publication date: 11 April 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-01068-x

zbMATH Keywords

random walksmixing timeleader electionconductancecongest model

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Uses Software

• Pastry

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Leader election in ad hoc radio networks: a keen ear helps
• Sublinear bounds for randomized leader election
• Mixing times are hitting times of large sets
• Knowledge, level of symmetry, and time of leader election
• The isoperimetric number of random regular graphs
• Efficient elections in chordal ring networks
• Improved bounds for electing a leader in a synchronous ring
• Fast Byzantine leader election in dynamic networks
• Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds
• Impact of knowledge on election time in anonymous networks
• Probabilistic quorum systems
• Randomized leader election
• Expander graphs and their applications
• Electing a leader in a synchronous ring
• The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• An improved algorithm for decentralized extrema-finding in circular configurations of processes
• Distributed Computing: A Locality-Sensitive Approach
• Design and analysis of dynamic leader election protocols in broadcast networks
• Leader Election in Well-Connected Graphs
• Probability and Computing
• On the Complexity of Universal Leader Election

This page was built for publication: Leader election in well-connected graphs