SCIENCE@home

Making evildoers pay: resource-competitive broadcast in sensor networks

Seth Gilbert,Maxwell Young

Published 2012 in ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

ABSTRACT

Consider a time-slotted, single-hop, wireless sensor network consisting of <i>n</i> correct devices and and <i>f</i>•<i>n</i> Byzantine devices where <i>f</i>≥0 is any constant; the Byzantine devices may or may not outnumber the correct ones. There exists a trusted sender Alice who wishes to deliver a message <i>m</i> over a single channel to the correct devices. There is also an evil user Carol who controls the Byzantine devices and uses them to disrupt the communication channel. For a constant <i>k</i>≥2, the correct and Byzantine devices each possess a meager energy budget of <i>O</i>(<i>n</i><sup>1/<i>k</i></sup>), Alice and Carol each possess a limited budget of <i>Õ</i>(<i>n</i><sup>1/<i>k</i></sup>), and sending or listening in a slot incurs unit cost. This setup captures the inherent challenges of guaranteeing communication despite scarce resources and attacks on the network. Given this Alice versus Carol scenario, we ask: Is communication of <i>m</i> feasible and, if so, at what cost? We develop a protocol which, for an arbitrarily small constant <i>ε</i>>0, ensures that at least (1-ε)<i>n</i> correct devices receive <i>m</i> with high probability. Furthermore, if Carol's devices expend <i>T</i> energy jamming the channel, then Alice and the correct devices each spend only <i>Õ</i>(<i>T</i><sup>1/(<i>k</i>+1)</sup>). In other words, delaying the transmission of <i>m</i> forces a jamming adversary to rapidly deplete its energy supply and, consequently, cease attacks on the network.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

CONCEPTS

REFERENCES

Showing 1-30 of 30 references · Page 1 of 1

CITED BY

Showing 1-27 of 27 citing papers · Page 1 of 1