Interference-resilient information exchange

Seth Gilbert, Rachid Guerraoui, Dariusz R. Kowalski, Calvin Newport

Research output: Chapter in Book/Report/Conference proceedingConference contribution

47 Scopus citations


This paper presents an efficient protocol for reliably exchanging information in a single-hop, multi-channel radio network subject to unpredictable interference. We model the interference by an adversary that can simultaneously disrupt up to t of the C available channels. We assume no shared secret keys or third-party infrastructure. The running time of our protocol depends on the gap between C and t: when the number of channels C =Ω(t2), the running time is linear; when only C = t+1 channels are available, the running time is exponential. We prove that exponential-time is unavoidable in the latter case. At the core of our protocol lies a combinatorial function, possibly of independent interest, described for the first time in this paper: the multi-selector. A multi-selector generates a sequence of channel assignments for each device such that every sufficiently large subset of devices is partitioned onto distinct channels by at least one of these assignments.

Original languageEnglish (US)
Title of host publicationIEEE INFOCOM 2009 - The 28th Conference on Computer Communications
Number of pages9
StatePublished - 2009
Externally publishedYes
Event28th Conference on Computer Communications, IEEE INFOCOM 2009 - Rio de Janeiro, Brazil
Duration: Apr 19 2009Apr 25 2009

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Conference28th Conference on Computer Communications, IEEE INFOCOM 2009
CityRio de Janeiro

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering

Cite this