On the Complexity of Universal Leader Election
DOI10.1145/2699440zbMath1321.68285OpenAlexW2042437235MaRDI QIDQ5501952
Amitabh Trehan, Peter Robinson, Shay Kutten, Gopal Pandurangan, David Peleg
Publication date: 14 August 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://pure.qub.ac.uk/en/publications/on-the-complexity-of-universal-leader-election(3e022c01-3fba-41be-b286-2dfbb05f7515).html
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14) Randomized algorithms (68W20) Distributed algorithms (68W15)
Related Items (18)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sublinear bounds for randomized leader election
- Knowledge, level of symmetry, and time of leader election
- Distributed algorithms. 8th international workshop, WDAG 1994, Terschelling, The Netherlands, September 29 -- October 1, 1994. Proceedings
- Size-estimation framework with applications to transitive closure and reachability
- 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
- Design and Analysis of Distributed Algorithms
- A trade-off between information and communication in broadcast protocols
- Electing a leader in a synchronous ring
- Distributed Computing: A Locality-Sensitive Approach
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Probability and Computing
- Efficient distributed approximation algorithms via probabilistic tree embeddings
This page was built for publication: On the Complexity of Universal Leader Election