Of Malicious Motes and Suspicious Sensors
How much damage can a malicious tiny device cause in a single-hopwireless network? Imagine two players, Alice and Bob, who want toexchange information. Collin, a malicious adversary, wants to preventthem from communicating. By broadcasting at the same time as Alice orBob, Collin can destroy their...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Language: | en_US |
| Published: |
2006
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/32534 |
| _version_ | 1811071285775564800 |
|---|---|
| author | Gilbert, Seth Guerraoui, Rachid Newport, Calvin |
| author2 | Nancy Lynch |
| author_facet | Nancy Lynch Gilbert, Seth Guerraoui, Rachid Newport, Calvin |
| author_sort | Gilbert, Seth |
| collection | MIT |
| description | How much damage can a malicious tiny device cause in a single-hopwireless network? Imagine two players, Alice and Bob, who want toexchange information. Collin, a malicious adversary, wants to preventthem from communicating. By broadcasting at the same time as Alice orBob, Collin can destroy their messages or overwhelm them with his ownmalicious data. Being a tiny device, however, Collin can onlybroadcast up to B times. Given that Alice and Bob do not knowB, and cannot distinguish honest from malicious messages, howlong can Collin prevent them from communicating? We show the answerto be 2B + Theta(lg|V|) communication rounds, where V is theset of values that Alice and Bob may transmit. We prove this resultto be optimal by deriving an algorithm that matches our lowerbound---even in the stronger case where Alice and Bob do not start thegame at the same time.We then argue that this specific 3-player game captures the generalextent to which a malicious adversary can disrupt coordination in asingle-hop wireless network. We support this claim by deriving---via reduction from the 3-player game---round complexity lower boundsfor several classical n-player problems: 2B + Theta(lg|V|) for reliable broadcast,2B + Omega(lg(n/k)) for leader election among k contenders,and 2B + Omega(k*lg(|V|/k)) for static k-selection. We then consider an extension of our adversary model that also includes up to t crash failures. We study binary consensus as the archetypal problem for this environment and show a bound of 2B + Theta(t) rounds. We conclude by providing tight, or nearly tight, upper bounds for all four problems. The new upper and lower bounds in this paper represent the first such results for a wireless network in which the adversary has the ability to disrupt communication. |
| first_indexed | 2024-09-23T08:48:47Z |
| id | mit-1721.1/32534 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:48:47Z |
| publishDate | 2006 |
| record_format | dspace |
| spelling | mit-1721.1/325342019-04-10T19:12:09Z Of Malicious Motes and Suspicious Sensors Gilbert, Seth Guerraoui, Rachid Newport, Calvin Nancy Lynch Theory of Computation wireless ad hoc networks byzantine reliable broadcast leader election k-selection consensus collision detection How much damage can a malicious tiny device cause in a single-hopwireless network? Imagine two players, Alice and Bob, who want toexchange information. Collin, a malicious adversary, wants to preventthem from communicating. By broadcasting at the same time as Alice orBob, Collin can destroy their messages or overwhelm them with his ownmalicious data. Being a tiny device, however, Collin can onlybroadcast up to B times. Given that Alice and Bob do not knowB, and cannot distinguish honest from malicious messages, howlong can Collin prevent them from communicating? We show the answerto be 2B + Theta(lg|V|) communication rounds, where V is theset of values that Alice and Bob may transmit. We prove this resultto be optimal by deriving an algorithm that matches our lowerbound---even in the stronger case where Alice and Bob do not start thegame at the same time.We then argue that this specific 3-player game captures the generalextent to which a malicious adversary can disrupt coordination in asingle-hop wireless network. We support this claim by deriving---via reduction from the 3-player game---round complexity lower boundsfor several classical n-player problems: 2B + Theta(lg|V|) for reliable broadcast,2B + Omega(lg(n/k)) for leader election among k contenders,and 2B + Omega(k*lg(|V|/k)) for static k-selection. We then consider an extension of our adversary model that also includes up to t crash failures. We study binary consensus as the archetypal problem for this environment and show a bound of 2B + Theta(t) rounds. We conclude by providing tight, or nearly tight, upper bounds for all four problems. The new upper and lower bounds in this paper represent the first such results for a wireless network in which the adversary has the ability to disrupt communication. 2006-04-19T17:01:59Z 2006-04-19T17:01:59Z 2006-04-19 MIT-CSAIL-TR-2006-026 http://hdl.handle.net/1721.1/32534 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 20 p. 22447191 bytes 841434 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | wireless ad hoc networks byzantine reliable broadcast leader election k-selection consensus collision detection Gilbert, Seth Guerraoui, Rachid Newport, Calvin Of Malicious Motes and Suspicious Sensors |
| title | Of Malicious Motes and Suspicious Sensors |
| title_full | Of Malicious Motes and Suspicious Sensors |
| title_fullStr | Of Malicious Motes and Suspicious Sensors |
| title_full_unstemmed | Of Malicious Motes and Suspicious Sensors |
| title_short | Of Malicious Motes and Suspicious Sensors |
| title_sort | of malicious motes and suspicious sensors |
| topic | wireless ad hoc networks byzantine reliable broadcast leader election k-selection consensus collision detection |
| url | http://hdl.handle.net/1721.1/32534 |
| work_keys_str_mv | AT gilbertseth ofmaliciousmotesandsuspicioussensors AT guerraouirachid ofmaliciousmotesandsuspicioussensors AT newportcalvin ofmaliciousmotesandsuspicioussensors |