How to Elect a Low-energy Leader
Preprint
Abstract
In many networks of wireless devices the scarcest resource is energy, and the lion's share of energy is often spent on sending and receiving packets. In this paper we present a comprehensive study of the energy complexity of fundamental problems in wireless networks with four different levels of collision detection: Strong-CD (in which transmitters and listeners detect collisions), Sender-CD (in which transmitters detect collisions, indirectly), Receiver-CD (in which listeners detect collisions), and No-CD (in which no one detects collisions). We show that the randomized energy complexity of Approximate Counting and Leader Election is $\Omega(\log^* n)$ in Sender-CD and No-CD but $\Omega(\log(\log^* n))$ in Strong-CD and Receiver-CD, and also provide matching upper bounds. This establishes an exponential separation between the Sender-CD and Receiver-CD models, and also confirms that the recent $O(\log(\log^* n))$ Contention Resolution protocol of Bender et al. (STOC 2016) is optimal in Strong-CD. In the deterministic setting, all $n$ devices have unique IDs in the range $[N]$. We establish another exponential separation between the deterministic Sender-CD and Receiver-CD models in the opposite direction. We show that Leader Election can be solved with $O(\log \log N)$ energy in the deterministic Sender-CD model, and give a matching $\Omega(\log \log N)$ energy lower bound in the Strong-CD model. However, in Receiver-CD and No-CD the energy complexity of these problems jumps to $\Theta(\log N)$. For the special case where $n = \Theta(N)$, we prove that Leader Election can be solved with only $O(\alpha(N))$ energy in No-CD. To our best knowledge, this is the first time the inverse-Ackermann function appears in the field of distributed computing.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- A Modular 1 mm$^{3}$ Die-Stacked Sensing Platform With Low Power I$^{2}$C Inter-Die Communication and Multi-Modal Energy HarvestingIEEE Journal of Solid-State Circuits, 2012
- Leader election using loneliness detectionDistributed Computing, 2012
- Broadcasting in undirected ad hoc radio networksDistributed Computing, 2005
- Weak communication in single‐hop radio networks: adjusting algorithms to industrial standardsConcurrency and Computation: Practice and Experience, 2003
- Distributed broadcast in radio networks of unknown topologyTheoretical Computer Science, 2003
- Randomized initialization protocols for ad hoc networksIEEE Transactions on Parallel and Distributed Systems, 2000
- Energy-efficient initialization protocols for single-hop radio networks with no collision detectionIEEE Transactions on Parallel and Distributed Systems, 2000
- On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomizationJournal of Computer and System Sciences, 1992
- Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detectionDistributed Computing, 1991
- Log-Logarithmic Selection Resolution Protocols in a Multiple Access ChannelSIAM Journal on Computing, 1986