Sublinear bounds for randomized leader election

DOI10.1016/j.tcs.2014.02.009zbMath1303.68034arXiv1210.4822OpenAlexW2069689700MaRDI QIDQ477103

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

Publication date: 2 December 2014

Published in: Theoretical Computer Science, Distributed Computing and Networking (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1210.4822

zbMATH Keywords

randomizationlower bounddistributed algorithmleader election

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (11)

Tight bounds for distributed minimum-weight spanning tree verification ⋮ Improved deterministic leader election in diameter-two networks ⋮ Termination of amnesiac flooding ⋮ Improved Tradeoffs for Leader Election ⋮ Leader election in well-connected graphs ⋮ Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds ⋮ The complexity of leader election in diameter-two networks ⋮ Message lower bounds via efficient network synchronization ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ On the Complexity of Universal Leader Election ⋮ Performance and robustness of discrete and finite time average consensus algorithms

Uses Software

• Pastry

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• Randomized leader election
• Distributed agreement in dynamic peer-to-peer networks
• Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks
• Design and Analysis of Distributed Algorithms
• Low Communication Self-stabilization through Randomization
• 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
• Time, clocks, and the ordering of events in a distributed system
• Distributed Computing: A Locality-Sensitive Approach
• Efficient leader election using sense of direction
• Probabilistic quorum systems
• Efficient distributed approximation algorithms via probabilistic tree embeddings

This page was built for publication: Sublinear bounds for randomized leader election