• Calendar

April 8, Tuesday
14:00 – 16:00

Wireless networks are particularly susceptible to malicious and malfunctioning devices. For example, a malicious device can easily jam the airwaves, disrupting all communication. In this talk, I will present new techniques for overcoming network disruptions in wireless networks, specifically in the context of multi-channel networks. In order to provide some intuition as to the challenges posed by malicious disruption, I will begin by demonstrating a lower bound for oblivious gossip algorithms. (Underlying the lower bound proof lies an interesting connection between epsilon-gossip and extremal graph theory.) I will then present an adaptive algorithm that improves on the lower bound, relying on a new combinatorial tool, the multiselector (which, as a natural generalization of a selector, we believe to be of potentially independent interest). Finally, I will present a randomized algorithm that can tolerate even more severe forms of malicious misbehavior. Joint work with Shlomi Dolev, Rachid Guerraoui, Darek Kowalski and Calvin Newport