Exponential Separations in the Energy Complexity of Leader Election
Preprint
Abstract
Energy is often the most constrained resource for battery-powered wireless devices and the lion's share of energy is often spent on transceiver usage (sending/receiving packets), not on computation. In this paper we study the energy complexity of LeaderElection and ApproximateCounting in several models of wireless radio networks. It turns out that energy complexity is very sensitive to whether the devices can generate random bits and their ability to detect collisions. We consider four collision-detection models: Strong-CD (in which transmitters and listeners detect collisions), Sender-CD and Receiver-CD (in which only transmitters or only listeners detect collisions), and No-CD (in which no one detects collisions.) The take-away message of our results is quite surprising. For randomized LeaderElection algorithms, there is an exponential gap between the energy complexity of Sender-CD and Receiver-CD, and for deterministic LeaderElection algorithms there is another exponential gap, but in the reverse direction. In particular, the randomized energy complexity of LeaderElection is $\Theta(\log^* n)$ in Sender-CD but $\Theta(\log(\log^* n))$ in Receiver-CD, where $n$ is the (unknown) number of devices. Its deterministic complexity is $\Theta(\log N)$ in Receiver-CD but $\Theta(\log\log N)$ in Sender-CD, where $N$ is the (known) size of the devices' ID space. There is a tradeoff between time and energy. We give a new upper bound on the time-energy tradeoff curve for randomized LeaderElection and ApproximateCounting. A critical component of this algorithm is a new deterministic LeaderElection algorithm for dense instances, when $n=\Theta(N)$, with inverse-Ackermann-type ($O(\alpha(N))$) energy complexity.
Keywords
All Related Versions
This publication has 13 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
- A lower bound for radio broadcastJournal of Computer and System Sciences, 1991
- Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detectionDistributed Computing, 1991