On the Complexity of Universal Leader Election
DOI10.1145/2699440zbMATH Open1321.68285OpenAlexW2042437235MaRDI QIDQ5501952FDOQ5501952
Authors: Shay Kutten, Gopal Pandurangan, Peter Robinson, Amitabh Trehan, 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
Recommendations
- On the complexity of universal leader election
- Singularly optimal randomized leader election
- The complexity of leader election in diameter-two networks
- Simple and efficient leader election in the full information model
- Leader election in complete networks
- Leader Election in Complete Networks
- On space and time complexity of loosely-stabilizing leader election
- Asymptotic properties of a leader election algorithm
- A probabilistic analysis of a leader election algorithm
- Exponential separations in the energy complexity of leader election
Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15) Distributed systems (68M14)
Cites Work
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Probability and Computing
- Title not available (Why is that?)
- 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
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Distributed algorithms. 8th international workshop, WDAG 1994, Terschelling, The Netherlands, September 29 -- October 1, 1994. Proceedings
- Efficient distributed approximation algorithms via probabilistic tree embeddings
Cited In (27)
- Leader election in well-connected graphs
- Near-optimal knowledge-free resilient leader election
- Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
- On the complexity of universal leader election
- Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds
- Latency, capacity, and distributed minimum spanning trees
- Distributed computation of exact average degree and network size in finite time under quantized communication
- Communication costs in a geometric communication network
- Message lower bounds via efficient network synchronization
- Message Lower Bounds via Efficient Network Synchronization
- Leader election in well-connected graphs
- Improved deterministic leader election in diameter-two networks
- How to elect a leader faster than a tournament
- Deterministic leader election in \(O(D+\log n)\) time with messages of size \(O(1)\)
- Sublinear message bounds for randomized agreement
- Improved Tradeoffs for Leader Election
- Smoothed Analysis of Leader Election in Distributed Networks
- The topology of randomized symmetry-breaking distributed computing
- Singularly optimal randomized leader election
- Termination of amnesiac flooding
- Transmitting once to elect a leader on wireless networks
- The complexity of leader election in diameter-two networks
- Randomized leader election
- Distributed MST and broadcast with fewer messages, and faster gossiping
- Time-message trade-offs in distributed algorithms
- Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
- Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
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 Q5501952)
