Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Energy-efficient Leader Election in Wireless Networks
Speaker:Yi-Jun Chang
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (others' work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Monday, 14 November 2016
Duration:30 Minutes
Building: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.

Name(s):Christoph Lenzen
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Christoph Lenzen, 10/14/2016 10:32 AM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Christoph Lenzen, 10/14/2016 10:32 AM -- Created document.