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.

Published in:
Proceedings of the 10th International Conference On Principles Of Distributed Systems (OPODIS '06)
Presented at:
OPODIS 2006, Bordeaux, France, December 12-15, 2006

Note: The status of this file is: Anyone

 Record created 2006-10-05, last modified 2020-07-30

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)