AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

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.
https://arxiv.org/abs/1609.08486

Christoph Lenzen

--email hidden

passcode not visible

logged in users only