Multi-Message Broadcast with Abstract MAC Layers and Unreliable Links

Friday, February 21, 2014 - 11:00am to 12:30pm
Mohsen Ghaffari and Erez Kantor

We study the multi-message broadcast problem using abstract MAC layer models
of wireless networks. These models capture the key guarantees of existing MAC layers
while abstracting away low-level details such as signal propagation and contention.
We begin by studying upper and lower bounds for this problem in a {\em standard abstract
MAC layer model}---identifying an interesting dependence between the structure
of unreliable links and achievable time complexity. In more detail, given a restriction that devices connected directly by an unreliable link are not too far from each other in the reliable link topology, we can (almost) match the efficiency of the reliable case.
For the related restriction, however, that two devices connected by an unreliable link are not
too far from each other in geographic distance, we prove a new lower bound that shows that this efficiency is impossible.

We then investigate how much extra power must be added to the model to enable
solutions of a new order of magnitude of efficiency. We describe a new {\em enhanced abstract MAC layer model} and present a new multi-message broadcast algorithm that (under certain natural assumptions) solves the problem faster than any known solutions in an abstract MAC layer setting.