TITLE: Interference-Resilient Information Exchange
SPEAKER: Calvin Newport (MIT)
PLACE: 32-G531
TIME:   1-2:30pm
DATE:   Friday April 17th, 2009


ABSTRACT:
 This talk presents an efficient protocol to reliably exchange
 information in a single-hop radio network with unpredictable
 interference.  The devices can access $C$ communication channels.
 We model the interference with an adversary that can disrupt up
 to $t$ of these channels simultaneously.
 We assume no
 shared secret keys or third-party infrastructure.  The running time
 of our protocol decreases as the gap between $C$ and $t$ increases.
 Two extreme cases prove particularly interesting: The running time
 is linear when the number of channels $C =\Omega(t^2)$, and
 exponential when only $C = t+1$ channels are available.  We prove
 that exponential-time is unavoidable in the latter case.

 At the core of our protocol lies a combinatorial function, of
 independent interest, and described for the first time in this
 paper: the multi-selector. This function determines a
 sequence of device channel assignments such that every sufficiently
 large subset of devices is partitioned, by at least one of these
 assignments, onto distinct channels.

 This is joint work with: Seth Gilbert, Rachid Guerraoui, and Darek Kowalski