Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election

DOI10.1145/3614429arXiv2105.07518OpenAlexW4385720197MaRDI QIDQ6052028

Yi-Jun Chang, Ran Duan, Shunhua Jiang

Publication date: 23 October 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

radio networkleader electiontime-energy trade-off

Mathematics Subject Classification ID

Computer science (68-XX)

Related Items (2)

The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection
• A lower bound for radio broadcast
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Distributed broadcast in radio networks of unknown topology.
• Probabilistic algorithms for the wake-up problem in single-hop radio networks
• Transmitting once to elect a leader on wireless networks
• Deterministic non-adaptive contention resolution on a shared channel
• Tree algorithms for packet broadcast channels
• Unbounded Contention Resolution in Multiple-Access Channels
• Adversarial Queuing on the Multiple Access Channel
• Simple Distributed Spanners in Dense Congest Networks
• Lower Bounds for Clear Transmissions in Radio Networks
• A perspective on multiaccess channels
• Log-Logarithmic Selection Resolution Protocols in a Multiple Access Channel
• A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels
• Estimating the multiplicities of conflicts to speed their resolution in multiple access channels
• An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks
• Weak communication in single‐hop radio networks: adjusting algorithms to industrial standards
• Analysis of Backoff Protocols for Multiple Access Channels
• Exponential Separations in the Energy Complexity of Leader Election
• Efficient algorithms for leader election in radio networks
• On selection problem in radio networks
• An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels
• The Energy Complexity of Broadcast
• Contention resolution with log-logstar channel accesses
• A Faster Distributed Radio Broadcast Primitive
• Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks
• Asynchronous Shared Channel
• Contention resolution with constant expected delay
• Broadcasting algorithms in radio networks with unknown topology
• Radio Network Lower Bounds Made Easy
• Fast Nonadaptive Deterministic Algorithm for Conflict Resolution in a Dynamic Multiple-Access Channel
• Near Optimal Leader Election in Multi-Hop Radio Networks
• Sleeping is Efficient: MIS in O (1)-rounds Node-averaged Awake Complexity
• The Energy Complexity of BFS in Radio Networks
• Broadcasting in undirected ad hoc radio networks
• Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks

This page was built for publication: Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election