Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Of Malicious Motes and Suspicious Sensors: On the Efficiency of Malicious Interference in Wireless Networks
 
conference paper

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

Gilbert, Seth  
•
Guerraoui, Rachid  
•
Newport, Calvin
2006
Theoretical Computer Science
10th International Conference on Principles of Distributed Systems

How efficiently can a malicious device disrupt a single-hop wireless network? Imagine two honest players attempting to exchange information in the presence of a malicious adversary that can disrupt communication by jamming or overwriting messages. Assume the adversary has a broadcast budget of beta-unknown to the honest players. We show that communication can be delayed for 2 beta + Theta(Ig vertical bar V vertical bar) rounds, where V is the set of values that the honest players may transmit. We then derive, via reduction to this 3-player game, round complexity lower bounds for several classical n-player problems: 2 beta + Omega(Ig vertical bar V vertical bar) for reliable broadcast, 2 beta + Omega(log n) for leader election, and 2 beta + Omega(k Ig vertical bar V vertical bar/k) for static k-selection. We also consider an extension of our adversary model that includes up to t crash failures. Here we show a bound of 2 beta + Theta(t) rounds for binary consensus. We provide tight, or nearly tight, upper bounds for all four problems. From these results we can derive bounds oil the efficiency of malicious disruption, stated in terms of two new metrics: jamming gain (the ratio of rounds delayed to adversarial broadcasts) and disruption-free complexity (the rounds required to terminate in the special case of no disruption). Two key conclusions of this study: ( 1) all the problems considered feature semantic vulnerabilities that allow an adversary to disrupt termination more efficiently than simple jamming (i.e., all have a jamming gain greater than 1): and (2) for all the problems considered, the round complexity grows linearly with the number of bits to be communicated (i.e., all have a Omega(Ig vertical bar V vertical bar) or Omega(Ig n) disruption-free complexity.)

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

main.pdf

Access type

openaccess

Size

308.22 KB

Format

Adobe PDF

Checksum (MD5)

067d0a3940042cf1641be2720136d284

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés