Please use this identifier to cite or link to this item:
|Title:||Making evildoers pay: Resource-competitive broadcast in sensor networks|
|Authors:||Gilbert, S. |
|Keywords:||byzantine fault tolerance|
resource competitive analysis
wireless sensor networks
|Citation:||Gilbert, S.,Young, M. (2012). Making evildoers pay: Resource-competitive broadcast in sensor networks. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing : 145-154. ScholarBank@NUS Repository. https://doi.org/10.1145/2332432.2332461|
|Abstract:||Consider a time-slotted, single-hop, wireless sensor network consisting of n correct devices and and f·n Byzantine devices where f ≥ 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 m 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 k ≥ 2, the correct and Byzantine devices each possess a meager energy budget of O(n 1/k), Alice and Carol each possess a limited budget of Õ;(n 1/k), 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 m feasible and, if so, at what cost? We develop a protocol which, for an arbitrarily small constant ε > 0, ensures that at least (1-ε)n correct devices receive m with high probability. Furthermore, if Carol's devices expend T energy jamming the channel, then Alice and the correct devices each spend only Õ(T 1/(k+1)). In other words, delaying the transmission of m forces a jamming adversary to rapidly deplete its energy supply and, consequently, cease attacks on the network. © 2012 ACM.|
|Source Title:||Proceedings of the Annual ACM Symposium on Principles of Distributed Computing|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Feb 11, 2019
checked on Feb 2, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.