We show that the randomized energy complexity of leader election in Sender-CD and No-CD is Θ(log*n) but Θ(log(log*n)) in Strong-CD and Receiver-CD. Our lower bound confirms that the recent O(log(log*n)) contention resolution protocol of Bender et al. (STOC 2016) is optimal.
In the deterministic setting, all n devices have unique IDs in the range [N]. We prove that the energy complexity of leader election in Receiver-CD and No-CD is Θ(log N) but Θ(log log N) in Strong-CD and Sender-CD. For the special case where n = Θ(N), we prove that leader election can be solved with only O(α(N)) energy in No-CD.
Joint work with Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, and Wei Zhan.
https://arxiv.org/abs/1609.08486