Abstract
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. 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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Brown, T.X., James, J.E., Sethi, A.: Jamming and sensing of encrypted wireless ad hoc networks. Technical Report CU-CS-1005-06, UC Boulder (2006)
Perrig, A., Szewczyk, R., Tygar, J.D., Wen, V., Culler, D.E.: Spins: Security protocols for sensor networks. Wireless Networks 8(5), 521–534 (2002)
Karlof, C., Sastry, N., Wagner, D.: Tinysec: A link layer security architecture for wireless sensor networks. In: Embedded Networked Sensor Systems (2004)
Koo, C.Y.: Broadcast in radio networks tolerating byzantine adversarial behavior. In: Principles of Distributed Computing, pp. 275–282 (2004)
Bhandari, V., Vaidya, N.H.: On reliable broadcast in a radio network. In: Principles of Distributed Computing, pp. 138–147 (2005)
Pelc, A., Peleg, D.: Broadcasting with locally bounded byzantine faults. Information Processing Letters 93(3), 109–115 (2005)
Drabkin, V., Friedman, R., Segal, M.: Efficient byzantine broadcast in wireless ad hoc networks. In: Dependable Systems and Networks, pp. 160–169 (2005)
Pelc, A., Peleg, D.: Feasibility and complexity of broadcasting with random transmission failures. In: Principles of Distributed Computing, pp. 334–341 (2005)
Clementi, A.E.F., Monti, A., Silvestri, R.: Optimal F-reliable protocols for the do-all problem on single-hop wireless networks. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 320–331. Springer, Heidelberg (2002)
Chlebus, B.S., Kowalski, D.R., Lingas, A.: The do-all problem in broadcast networks. In: Principles of Distributed Computing, pp. 117–127 (2001)
Kranakis, E., Krizanc, D., Pelc, A.: Fault-tolerant broadcasting in radio networks. In: European Symposium on Algorithms, pp. 283–294 (1998)
Clementi, A., Monti, A., Silvestri, R.: Round robin is optimal for fault-tolerant broadcasting on wireless networks. J. Parallel Distributed Computing 64(1), 89–96 (2004)
Koo, C.Y., Bhandari, V., Katz, J., Vaidya, N.H.: Relibable broadcast in radio networks: The bounded collision case. In: Principles of Distributed Computing (2006)
Stahlberg, M.: Radio jamming attacks against two popular mobile networks. In: Helsinki University of Technology Seminar on Network Security (2000)
Negi, R., Perrig, A.: Jamming analysis of mac protocols. Technical report, Carnegie Mellon University (2003)
Hu, Y., Perrig, A.: A survey of secure wireless ad hoc routing. IEEE Security and Privacy Magazine 02(3), 28–39 (2004)
Gupta, V., Krishnamurthy, S., Faloutsos, S.: Denial of service attacks at the mac layer in wireless ad hoc networks. In: Military Communications Conference (2002)
Abramson, N.: The aloha system - another approach for computer communications. In: Proceedings of Fall Joint Computer Conference, AFIPS, vol. 37, pp. 281–285 (1970)
Metcalf, R.M., Boggs, D.R.: Ethernet: Distributed packet switching for local computer networks. Communications of the ACM 19(7), 395–404 (1976)
Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. Journal of Computer and System Sciences 45(1), 104–126 (1992)
Woo, A., Whitehouse, K., Jiang, F., Polastre, J., Culler, D.: Exploiting the capture effect for collision detection and recovery. In: Workshop on Embedded Networked Sensors, pp. 45–52 (2005)
Clementi, A., Monti, A., Silvestri, R.: Selective families, superimposed codes, and broadcasting on unknown radio networks. In: Symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 709–718 (2001)
Kowalski, D.R.: On selection problem in radio networks. In: Principles of Distributed Computing, pp. 158–166. ACM Press, New York (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gilbert, S., Guerraoui, R., Newport, C. (2006). Of Malicious Motes and Suspicious Sensors: On the Efficiency of Malicious Interference in Wireless Networks. In: Shvartsman, M.M.A.A. (eds) Principles of Distributed Systems. OPODIS 2006. Lecture Notes in Computer Science, vol 4305. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11945529_16
Download citation
DOI: https://doi.org/10.1007/11945529_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49990-9
Online ISBN: 978-3-540-49991-6
eBook Packages: Computer ScienceComputer Science (R0)