Campus Event Calendar

Event Entry

What and Who

Energy-efficient Leader Election in Wireless Networks

Yi-Jun Chang
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (others' work)
AG 1  
AG Audience

Date, Time and Location

Monday, 14 November 2016
30 Minutes
E1 4


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. Sophisticated collision detection technology costs money to put into wireless devices, so it is important to understand which type of collision detection technology is worth it in terms of algorithm performance. In this talk 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 formally prove that the sender-side (resp., receiver-side) collision detection technology leads to exponentially less energy consumption in the deterministic (resp., randomized) model.

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.


Christoph Lenzen
--email hidden
passcode not visible
logged in users only

Christoph Lenzen, 10/14/2016 10:32 -- Created document.