Of Malicious Motes and Suspicious Sensors
How efficiently can a malicious device disrupt communication in a wireless network? Imagine a basic game involving two honest players, Alice and Bob, who want to exchange information, and an adversary, Collin, who can disrupt communication using a limited budget of B broadcasts. How long can Collin delay Alice and Bob from communicating? In fact, the trials and tribulations of Alice and Bob capture the fundamental difficulty shared by several n-player problems, including reliable broadcast, leader election, static k-selection, and t-resilient consensus. We provide round complexity lower bounds—and (nearly) tight upper bounds—for each of those problems. These results imply bounds on adversarial efficiency, which we analyze in terms of jamming gain and disruption-free complexity.
2006
215
229
REVIEWED
EPFL
| Event name | Event place | Event date |
Bordeaux, France | December 12-15, 2006 | |