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

zbMATH Keywords

lower bounddistributed algorithmleader election

Mathematics Subject Classification ID

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)

Latency, capacity, and distributed minimum spanning trees ⋮ Communication costs in a geometric communication network ⋮ Improved deterministic leader election in diameter-two networks ⋮ Distributed computation of exact average degree and network size in finite time under quantized communication ⋮ Termination of amnesiac flooding ⋮ Improved Tradeoffs for Leader Election ⋮ Leader election in well-connected graphs ⋮ Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model ⋮ Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds ⋮ The complexity of leader election in diameter-two networks ⋮ Transmitting once to elect a leader on wireless networks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Message lower bounds via efficient network synchronization ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ Near-optimal knowledge-free resilient leader election ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree

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