{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:06:15Z","timestamp":1787504775418,"version":"build-2736575974"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,8,1]],"date-time":"2014-08-01T00:00:00Z","timestamp":1406851200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,8]]},"abstract":"<jats:p>\n                    This article studies the design of medium access control (MAC) protocols for wireless networks that are provably robust against arbitrary and unpredictable disruptions (e.g., due to unintentional external interference from co-existing networks or due to jamming). We consider a wireless network consisting of a set of\n                    <jats:italic>n<\/jats:italic>\n                    honest and reliable nodes within transmission (and interference) range of each other, and we model the external disruptions with a powerful adaptive adversary. This adversary may know the protocol and its entire history and can use this knowledge to jam the wireless channel at will at any time. It is allowed to jam a (1-\u03f5)-fraction of the timesteps, for an arbitrary constant \u03f5 &gt; 0 unknown to the nodes. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant (asymptotically optimal) throughput for the nonjammed time periods under any of the aforementioned adversarial strategies. The derived principles are also useful to build robust applications on top of the MAC layer, and we present an exemplary study for leader election, one of the most fundamental tasks in distributed computing.\n                  <\/jats:p>","DOI":"10.1145\/2635818","type":"journal-article","created":{"date-parts":[[2014,8,21]],"date-time":"2014-08-21T08:19:12Z","timestamp":1408609152000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Principles of Robust Medium Access and an Application to Leader Election"],"prefix":"10.1145","volume":"10","author":[{"given":"Baruch","family":"Awerbuch","sequence":"first","affiliation":[{"name":"The Johns Hopkins University, Baltimore, MD"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrea","family":"Richa","sequence":"additional","affiliation":[{"name":"Arizona State University, Tempe, AZ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Scheideler","sequence":"additional","affiliation":[{"name":"University of Paderborn, Paderborn Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"Telekom Innovation Laboratories (T-Labs) &amp; TU, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Arizona State University, Tempe, AZ"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,8,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298239.1298257"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0059"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28421"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400759"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201908)","author":"Bayraktaroglu E.","unstructured":"E. Bayraktaroglu , C. King , X. Liu , G. Noubir , R. Rajaraman , and B. Thapa . 2008. On the performance of IEEE 802.11 under jamming . In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201908) . 1265--1273. E. Bayraktaroglu, C. King, X. Liu, G. Noubir, R. Rajaraman, and B. Thapa. 2008. On the performance of IEEE 802.11 under jamming. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201908). 1265--1273."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1074023"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132905.1132919"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11476-2_10"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1287853.1287901"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146398"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.08.001"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/361179.361202"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582749"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Symposium on Distributed Computing (DISC\u201907)","author":"Dolev S.","unstructured":"S. Dolev , S. Gilbert , R. Guerraoui , and C. Newport . 2007a. Gossiping in a multi-channel radio network: An oblivious approach to coping with malicious interference . In Proceedings of the Symposium on Distributed Computing (DISC\u201907) . S. Dolev, S. Gilbert, R. Guerraoui, and C. Newport. 2007a. Gossiping in a multi-channel radio network: An oblivious approach to coping with malicious interference. In Proceedings of the Symposium on Distributed Computing (DISC\u201907)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400767"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 21st International Symposium on Distributed Computing (DISC\u201907)","author":"Dolev S.","unstructured":"S. Dolev , S. Gilbert , R. Guerraoui , and C. C. Newport . 2007b. Gossiping in a multi-channel radio network . In Proceedings of the 21st International Symposium on Distributed Computing (DISC\u201907) . 208--222. S. Dolev, S. Gilbert, R. Guerraoui, and C. C. Newport. 2007b. Gossiping in a multi-channel radio network. In Proceedings of the 21st International Symposium on Distributed Computing (DISC\u201907). 208--222."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/357195.357200"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00121-4"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201909)","author":"Gilbert S.","unstructured":"S. Gilbert , R. Guerraoui , D. Kowalski , and C. Newport . 2009a. Interference-resilient information exchange . In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201909) . S. Gilbert, R. Guerraoui, D. Kowalski, and C. Newport. 2009a. Interference-resilient information exchange. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201909)."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM\u201909)","author":"Gilbert S.","unstructured":"S. Gilbert , R. Guerraoui , D. R. Kowalski , and C. C. Newport . 2009b. Interference-Resilient information exchange . In Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM\u201909) . 2249--2257. S. Gilbert, R. Guerraoui, D. R. Kowalski, and C. C. Newport. 2009b. Interference-Resilient information exchange. In Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM\u201909). 2249--2257."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11945529_16"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355567"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792233828"},{"key":"e_1_2_1_25_1","series-title":"Chapter 8","volume-title":"Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance","author":"Hromkovic J.","year":"2005","unstructured":"J. Hromkovic , R. Klasing , A. Pelc , P. Ruzicka , and W. Unger . 2005 . Dissemination of Information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance ( Chapter 8 ). Springer-Verlag, New York , Chapter 8. J. Hromkovic, R. Klasing, A. Pelc, P. Ruzicka, and W. Unger. 2005. Dissemination of Information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance (Chapter 8). Springer-Verlag, New York, Chapter 8."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 9th International Workshop on Distributed Algorithms (WDAG\u201995)","author":"Itkis G.","unstructured":"G. Itkis , C. Lin , and J. Simon . 1995. Deterministic, constant space, self-stabilizing leader election on uniform rings . In Proceedings of the 9th International Workshop on Distributed Algorithms (WDAG\u201995) . 288--302. G. Itkis, C. Lin, and J. Simon. 1995. Deterministic, constant space, self-stabilizing leader election on uniform rings. In Proceedings of the 9th International Workshop on Distributed Algorithms (WDAG\u201995). 288--302."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146420"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/77606.77610"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of ESA.","author":"Kuhn F.","unstructured":"F. Kuhn , T. Moscibroda , and R. Wattenhofer . 2004. Radio network clustering from scratch . In Proceedings of ESA. F. Kuhn, T. Moscibroda, and R. Wattenhofer. 2004. Radio network clustering from scratch. In Proceedings of ESA."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/259380.259435"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2005.845533"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1102219.1102234"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1254882.1254896"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201907)","author":"Li M.","unstructured":"M. Li , I. Koutsopoulos , and R. Poovendran . 2007. Optimal jamming attacks and network defense policies in wireless sensor networks . In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201907) . 1307--1315. M. Li, I. Koutsopoulos, and R. Poovendran. 2007. Optimal jamming attacks and network defense policies in wireless sensor networks. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201907). 1307--1315."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201907)","author":"Liu X.","unstructured":"X. Liu , G. Noubir , R. Sundaram , and S. Tan . 2007. SPREAD: Foiling smart jammers using multi-layer agility . In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201907) . 2536--2540. X. Liu, G. Noubir, R. Sundaram, and S. Tan. 2007. SPREAD: Foiling smart jammers using multi-layer agility. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201907). 2536--2540."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02085-8_1"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 11th International Conference on Algorithms and Computation (ISAAC\u201900)","author":"Nakano K.","unstructured":"K. Nakano and S. Olariu . 2000. Randomized leader election protocols in radio networks with no collision detection . In Proceedings of the 11th International Conference on Algorithms and Computation (ISAAC\u201900) . Springer-Verlag, 362--373. K. Nakano and S. Olariu. 2000. Randomized leader election protocols in radio networks with no collision detection. In Proceedings of the 11th International Conference on Algorithms and Computation (ISAAC\u201900). Springer-Verlag, 362--373."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201907)","author":"Navda V.","unstructured":"V. Navda , A. Bohra , S. Ganguly , and D. Rubenstein . 2007. Using channel hopping to increase 802.11 resilience to jamming attacks . In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201907) . 2526--2530. V. Navda, A. Bohra, S. Ganguly, and D. Rubenstein. 2007. Using channel hopping to increase 802.11 resilience to jamming attacks. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201907). 2526--2530."},{"key":"e_1_2_1_39_1","unstructured":"R. Negi and A. Perrig. 2003. Jamming Analysis of MAC Protocols. Technical Report. Carnegie Mellon University.  R. Negi and A. Perrig. 2003. Jamming Analysis of MAC Protocols. Technical Report. Carnegie Mellon University."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2002.1003864"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073879"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795285333"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 24th International Symposium on Distributed Computing (DISC\u201910)","author":"Richa A.","unstructured":"A. Richa , C. Scheideler , S. Schmid , and J. Zhang . 2010. A jamming-resistant MAC protocol for multi-hop wireless networks . In Proceedings of the 24th International Symposium on Distributed Computing (DISC\u201910) . 179--193. A. Richa, C. Scheideler, S. Schmid, and J. Zhang. 2010. A jamming-resistant MAC protocol for multi-hop wireless networks. In Proceedings of the 24th International Symposium on Distributed Computing (DISC\u201910). 179--193."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2011.8"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332488"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"e_1_2_1_47_1","unstructured":"M. K. Simon J. K. Omura R. A. Schultz and B. K. Levin. 2001. Spread Spectrum Communications Handbook. McGraw-Hill.  M. K. Simon J. K. Omura R. A. Schultz and B. K. Levin. 2001. Spread Spectrum Communications Handbook. McGraw-Hill."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 2nd International Workshop on Sensor and Actor Network Protocols and Applications (SANPA\u201904)","author":"Smaragdakis G.","unstructured":"G. Smaragdakis , I. Matta , and A. Bestavros . 2004. SEP: A stable election protocol for clustered heterogeneous wireless sensor networks . In Proceedings of the 2nd International Workshop on Sensor and Actor Network Protocols and Applications (SANPA\u201904) . G. Smaragdakis, I. Matta, and A. Bestavros. 2004. SEP: A stable election protocol for clustered heterogeneous wireless sensor networks. In Proceedings of the 2nd International Workshop on Sensor and Actor Network Protocols and Applications (SANPA\u201904)."},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of MILCOM.","author":"Thuente D.","unstructured":"D. Thuente and M. Acharya . 2006. Intelligent jamming in wireless networks with applications to 802.11b and other networks . In Proceedings of MILCOM. D. Thuente and M. Acharya. 2006. Intelligent jamming in wireless networks with applications to 802.11b and other networks. In Proceedings of MILCOM."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215032"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of SECON.","author":"Wood A. D.","unstructured":"A. D. Wood , J. A. Stankovic , and G. Zhou . 2007. DEEJAM: Defeating energy-efficient jamming in IEEE 802.15.4-based wireless networks . In Proceedings of SECON. A. D. Wood, J. A. Stankovic, and G. Zhou. 2007. DEEJAM: Defeating energy-efficient jamming in IEEE 802.15.4-based wireless networks. In Proceedings of SECON."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/MNET.2006.1637931"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062689.1062697"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1023646.1023661"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2635818","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2635818","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:03:44Z","timestamp":1750259024000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2635818"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.1145\/2635818"],"URL":"https:\/\/doi.org\/10.1145\/2635818","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8]]},"assertion":[{"value":"2011-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}