How to Elect a Low-energy Leader.

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.