Of Malicious Motes and Suspicious Sensors On the Efficiency of Malicious Interference in Wireless Networks

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 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. The authors provide round complexity lower bounds - and (nearly) tight upper bounds - for each of those problems.