{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,3]],"date-time":"2026-01-03T21:05:24Z","timestamp":1767474324669,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":54,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642148484"},{"type":"electronic","value":"9783642148491"}],"license":[{"start":{"date-parts":[[2010,11,8]],"date-time":"2010-11-08T00:00:00Z","timestamp":1289174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2010,11,8]],"date-time":"2010-11-08T00:00:00Z","timestamp":1289174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-14849-1_11","type":"book-chapter","created":{"date-parts":[[2011,4,27]],"date-time":"2011-04-27T15:47:28Z","timestamp":1303919248000},"page":"319-350","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Coordination Problems in Ad Hoc Radio Networks"],"prefix":"10.1007","author":[{"given":"Dariusz R.","family":"Kowalski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,11,8]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1109\/TIT.1985.1057021","volume":"31","author":"N. Abramson","year":"1985","unstructured":"N. Abramson. Development of the alohanet, IEEE Transactions on Information Theory 31:119\u2013123, (1985).","journal-title":"IEEE Transactions on Information Theory"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/0022-0000(91)90015-W","volume":"43","author":"N. Alon","year":"1991","unstructured":"N. Alon, A. Bar-Noy, N. Linial, and D. Peleg. A lower bound for radio broadcast, Journal of Computer and System Sciences 43:290\u2013298, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"G. Alonso, E. Kranakis, C. Sawchuk, R. Wattenhofer, and P. Widmayer. Randomized protocols for node discovery in ad-hoc multichannel broadcast networks, In: Proceedings, 2nd Annual Conference on Adhoc Networks and Wireless (ADHOCNOW), volume 2865 of Lecture Notes in Computer Science. Springer, pages 104\u2013115, 2003.","DOI":"10.1007\/978-3-540-39611-6_10"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"H. Attiya and J. Welch. Distributed Computing, Wiley, 2004.","DOI":"10.1002\/0471478210"},{"key":"11_CR5","volume-title":"Algorithmic Number Theory","author":"E. Bach","year":"1996","unstructured":"E. Bach and J. Shallit. Algorithmic Number Theory, Volume I, The MIT Press, Cambridge, MA, 1996."},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/0022-0000(92)90042-H","volume":"45","author":"R. Bar-Yehuda","year":"1992","unstructured":"R. Bar-Yehuda, O. Goldreich, and A. Itai. On the time complexity of broadcast in radio networks: An exponential gap between determinism and randomization, Journal of Computer and System Sciences, 45:104\u2013126, 1992.","journal-title":"Journal of Computer and System Sciences"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/0222055","volume":"22","author":"R. Bar-Yehuda","year":"1993","unstructured":"R. Bar-Yehuda, A. Israeli, and A. Itai. Multiple communication in multihop radio networks, SIAM Journal on Computing, 22:875\u2013887, 1993.","journal-title":"SIAM Journal on Computing"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"M.A. Bender, M. Farach-Colton, S. He, B.C. Kuszmaul, and C.E. Leiserson. Adversarial contention resolution for simple channels, In: Proceedings, 17th Annual ACM Symposium on Parallel Algorithms (SPAA), pages 325\u2013332, 2005.","DOI":"10.1145\/1073970.1074023"},{"key":"11_CR9","unstructured":"M. Bienkowski, M. Klonowski, M. Korzeniowski, and D.R. Kowalski. Dynamic sharing of a multiple access channel, In: Proceedings, 27th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs 5 Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pages 83\u201394, to appear, 2010."},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/363647.363659","volume":"48","author":"A. Borodin","year":"2001","unstructured":"A. Borodin, J.M. Kleinberg, P. Raghavan, M. Sudan, and D.P. Williamson. Adversarial queuing theory, Journal of the ACM, 48:13\u201338, 2001.","journal-title":"Journal of the ACM"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1109\/TIT.1979.1056093","volume":"25","author":"J. Capetanakis","year":"1979","unstructured":"J. Capetanakis. Tree algorithms for packet broadcast channels. IEEE Transactions on Information Theory, 25:505\u2013515, 1979.","journal-title":"IEEE Transactions on Information Theory"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"1240","DOI":"10.1109\/TCOM.1985.1096245","volume":"33","author":"I. Chlamtac","year":"1985","unstructured":"I. Chlamtac and S. Kutten. On broadcasting in radio networks - problem analysis and protocol design, IEEE Transactions on Communications, 33:1240\u20131246, 1985.","journal-title":"IEEE Transactions on Communications"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s446-002-8028-1","volume":"15","author":"B.S. Chlebus","year":"2002","unstructured":"B.S. Chlebus, L. Gasieniec, A. Gibbons, A. Pelc, and W. Rytter. Deterministic broadcasting in unknown radio networks, Distributed Computing, 15:27\u201338, Springer, 2002.","journal-title":"Distributed Computing"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"B.S. Chlebus, L. Gasieniec, D. Kowalski, and T. Radzik. On the wake-up problem in radio networks, In: Proceedings, 32nd International Colloquium on Automata, Languages and Programming (ICALP), volume 3580 of Lecture Notes in Computer Science. Springer, Lisbon, Portugal, pages 347\u2013359, 2005.","DOI":"10.1007\/11523468_29"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"B.S. Chlebus and D. Kowalski. A better wake-up in radio networks, In: Proceedings, 23rd ACM Symposium on Principles of Distributed Computing (PODC), pages 266\u2013274, 2004.","DOI":"10.1145\/1011767.1011806"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/s00453-007-9123-5","volume":"54","author":"B.S. Chlebus","year":"2009","unstructured":"B.S. Chlebus, D.R. Kowalski, and T. Radzik. Many-to-many communication in radio networks, Algorithmica, 54:118\u2013139, 2009.","journal-title":"Algorithmica"},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"B.S. Chlebus, D.R. Kowalski, and M.A. Rokicki. Adversarial queuing on the multiple-access channel, In: Proceedings, 25th ACM Symposium on Principles of Distributed Computing (PODC), ACM, Denver, USA, pages 92\u2013101, 2006.","DOI":"10.1145\/1146381.1146398"},{"key":"11_CR18","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.tcs.2007.03.057","volume":"383","author":"B.S. Chlebus","year":"2007","unstructured":"B.S. Chlebus and M.A. Rokicki, Centralized asynchronous broadcast in radio networks, Theoretical Computer Science, 383:5\u201322, 2007.","journal-title":"Theoretical Computer Science"},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s00446-008-0056-2","volume":"21","author":"G. Chockler","year":"2008","unstructured":"G. Chockler, M. Demirbas, S. Gilbert, N.A. Lynch, C.C. Newport, and T. Nolte. Consensus and collision detectors in radio networks, Distributed Computing, 21:55\u201384, 2008.","journal-title":"Distributed Computing"},{"key":"11_CR20","doi-asserted-by":"publisher","first-page":"1453","DOI":"10.1137\/S0097539704442726","volume":"36","author":"M. Chrobak","year":"2007","unstructured":"M. Chrobak, L. Gasieniec, and D.R. Kowalski. The wake-up problem in multihop radio networks, SIAM Journal on Computing, 36:1453\u20131471, 2007.","journal-title":"SIAM Journal on Computing"},{"key":"11_CR21","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0196-6774(02)00004-4","volume":"43","author":"M. Chrobak","year":"2002","unstructured":"M. Chrobak, L. Gasieniec, and W. Rytter. Fast broadcasting and gossiping in radio networks, Journal of Algorithms, 43:177\u2013189, 2002.","journal-title":"Journal of Algorithms"},{"key":"11_CR22","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0304-3975(02)00851-4","volume":"302","author":"A.E.F. Clementi","year":"2003","unstructured":"A.E.F. Clementi, A. Monti, and R. Silvestri. Distributed broadcast in radio networks of unknown topology, Theoretical Computer Science, 302:337\u2013364, 2003.","journal-title":"Theoretical Computer Science"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"A.E.F. Clementi, A. Monti, and R. Silvestri. Round robin is optimal for fault-tolerant broadcasting on wireless networks, In: Proceedings, 9th Annual European Symposium on Algorithms (ESA), volume 2161 of Lecture Notes in Computer Science. Springer, Aarhus, Denmark, pages 452\u2013463, 2001.","DOI":"10.1007\/3-540-44676-1_38"},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"A. Czumaj and W. Rytter. Broadcasting algorithms in radio networks with unknown topology, In: Proceedings, 44th IEEE Symposium on Foundations of Computer Science (FOCS), EEE Computer Society, Cambridge, USA, pages 492\u2013501, 2003.","DOI":"10.1109\/SFCS.2003.1238222"},{"key":"11_CR25","doi-asserted-by":"crossref","unstructured":"J. Czyzowicz, L. Gasieniec, D.R. Kowalski, and A. Pelc. Consensus and mutual exclusion in a multiple access channel, In: Proceedings, (DISC), volume 5805 of Lecture Notes in Computer Science. Springer, Elche, Spain, pages 512\u2013526, 2009.","DOI":"10.1007\/978-3-642-04355-0_51"},{"key":"11_CR26","doi-asserted-by":"crossref","unstructured":"S. Dolev, S. Gilbert, R. Guerraoui, F. Kuhn, and C.C. Newport. The wireless synchronization problem, In: Proceedings, (PODC), ACM, Calgary, Canada, pages 190\u2013199, 2009.","DOI":"10.1145\/1582716.1582749"},{"key":"11_CR27","doi-asserted-by":"crossref","unstructured":"S. Dolev, S. Gilbert, R. Guerraoui, and C.C. Newport. Gossiping in a multi-channel radio network, In: Proceedings, (DISC), volume 4731 of Lecture Notes in Computer Science. Springer, Lemesos, Cyprus, pages 208\u2013222, 2007.","DOI":"10.1007\/978-3-540-75142-7_18"},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"M. Farach-Colton and M.A. Mosteiro. Initializing sensor networks of non-uniform density in the Weak Sensor Model, In: Proceedings, 10th International Workshop on Algorithms and Data Structures (WADS), volume 4619 of Lecture Notes in Computer Science. Springer, Halifax, Canada, pages 565\u2013576, 2007.","DOI":"10.1007\/978-3-540-73951-7_49"},{"key":"11_CR29","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1109\/TIT.1985.1057022","volume":"31","author":"R.G. Gallager","year":"1985","unstructured":"R.G. Gallager. A perspective on multiaccess channels, IEEE Transactions on Information Theory, 31:124\u2013142, 1985.","journal-title":"IEEE Transactions on Information Theory"},{"key":"11_CR30","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1137\/S0895480100376022","volume":"14","author":"L. Gasieniec","year":"2001","unstructured":"L. Gasieniec, A. Pelc, and D. Peleg. The wakeup problem in synchronous broadcast systems, SIAM Journal on Discrete Mathematics, 14:207\u2013222, 2001.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"11_CR31","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1145\/3828.214125","volume":"32","author":"A.G. Greenberg","year":"1985","unstructured":"A.G. Greenberg and S. Winograd. A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels, Journal of ACM 32:589\u2013596, 1985.","journal-title":"Journal of ACM"},{"key":"11_CR32","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1016\/j.tcs.2008.10.008","volume":"410","author":"S. Gilbert","year":"2009","unstructured":"S. Gilbert, R. Guerraoui, and C.C. Newport. Of malicious motes and suspicious sensors: On the efficiency of malicious interference in wireless networks, Theoretical Computer Science, 410:546\u2013569, 2009.","journal-title":"Theoretical Computer Science"},{"key":"11_CR33","doi-asserted-by":"crossref","unstructured":"O. Goussevskaia, Y.A. Oswald, and R. Wattenhofer. Complexity in geometric SINR, In: Proceedings, (MobiHoc), ACM, Montreal, Canada, pages 100\u2013109, 2007.","DOI":"10.1145\/1288107.1288122"},{"key":"11_CR34","doi-asserted-by":"publisher","first-page":"1178","DOI":"10.1109\/TCOM.1978.1094204","volume":"26","author":"J.F. Hayes","year":"1978","unstructured":"J.F. Hayes. An adaptive technique for local distribution, IEEE Transactions on Communications, 26:1178\u20131186, 1978.","journal-title":"IEEE Transactions on Communications"},{"key":"11_CR35","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/S0097539792233828","volume":"25","author":"J. Hrastad","year":"1996","unstructured":"J. Hrastad, T. Leighton, and B. Rogoff. Analysis of backoff protocols for multiple access channels, SIAM Journal on Computing, 25:740\u2013774, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"11_CR36","unstructured":"P. Indyk. Explicit constructions of selectors and related combinatorial structures, with applications, In: Proceedings, 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM\/SIAM, San Francisco, USA, pages 697\u2013704, 2002."},{"key":"11_CR37","doi-asserted-by":"crossref","unstructured":"T. Jurdzinski, M. Kutylowski, and J. Zatopianski. Efficient algorithms for leader election in radio networks, In: Proceedings, 21st Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 51\u201357, 2002.","DOI":"10.1145\/571825.571833"},{"key":"11_CR38","doi-asserted-by":"crossref","unstructured":"T. Jurdzinski and G. Stachowiak. Probabilistic algorithms for the wakeup problem in single-hop radio networks, In: Proceedings, 13th International Symposium on Algorithms and Computation (ISAAC), volume 2518 of Lecture Notes in Computer Science. Springer, Vancouver, Canada, pages 535\u2013549, 2002.","DOI":"10.1007\/3-540-36136-7_47"},{"key":"11_CR39","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1109\/TIT.1964.1053689","volume":"10","author":"W.H. Kautz","year":"1964","unstructured":"W.H. Kautz and R.R.C. Singleton. Nonrandom binary superimposed codes, IEEE Transactions on Information Theory, 10:363\u2013377, 1964.","journal-title":"IEEE Transactions on Information Theory"},{"key":"11_CR40","doi-asserted-by":"crossref","unstructured":"C.-Y. Koo, V. Bhandari, J. Katz, and N.H. Vaidya. Reliable broadcast in radio networks: The bounded collision case, In: Proceedings, 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM, Denver, USA, pages 258\u2013264, 2006.","DOI":"10.1145\/1146381.1146420"},{"key":"11_CR41","doi-asserted-by":"crossref","unstructured":"D. Kowalski, On selection problem in radio networks, In: Proceedings, 24th ACM Symposium on Principles of Distributed Computing (PODC), pages 158\u2013166, 2005.","DOI":"10.1145\/1073814.1073843"},{"key":"11_CR42","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1137\/S089548010342464X","volume":"18","author":"D.R. Kowalski","year":"2004","unstructured":"D.R. Kowalski and A. Pelc. Faster deterministic broadcasting in ad hoc radio networks, SIAM Journal on Discrete Mathematics 18:332\u2013346, 2004.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"11_CR43","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00446-005-0126-7","volume":"18","author":"D.R. Kowalski","year":"2005","unstructured":"D.R. Kowalski and A. Pelc. Deterministic broadcasting time in radio networks of unknown topology, Broadcasting in undirected ad hoc radio networks, Distributed Computing 18:43\u201357, Springer, 2005.","journal-title":"Distributed Computing"},{"key":"11_CR44","doi-asserted-by":"crossref","unstructured":"D.R. Kowalski and A. Pelc. Leader election in ad hoc radio networks: A keen ear helps, In: Proceedings, 32nd International Colloquium on Automata, Languages and Programming (ICALP), volume 5556 of Lecture Notes in Computer Science. Springer, Rhodes, Greece, pages 521\u2013533, 2009.","DOI":"10.1007\/978-3-642-02930-1_43"},{"key":"11_CR45","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1137\/S0097539794279109","volume":"27","author":"E. Kushilevitz","year":"1998","unstructured":"E. Kushilevitz and Y. Mansour. An $$\\varOmega(D \\log (N\/D))$$ lower bound for broadcast in radio networks, SIAM Journal on Computing, 27:702\u2013712, 1998.","journal-title":"SIAM Journal on Computing"},{"key":"11_CR46","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1145\/360248.360253","volume":"19","author":"R.M. Metcalfe","year":"1976","unstructured":"R.M. Metcalfe and D.R. Boggs. Ethernet: Distributed packet switching for local computer networks, Communications of the ACM, 19:395\u2013404, 1976.","journal-title":"Communications of the ACM"},{"key":"11_CR47","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1109\/TPDS.2002.1003864","volume":"13","author":"K. Nakano","year":"2002","unstructured":"K. Nakano, S. Olariu. Uniform leader election protocols for radio networks, IEEE Transactions on Parallel Distributed Systems, 13:516\u2013526, 2002.","journal-title":"IEEE Transactions on Parallel Distributed Systems"},{"key":"11_CR48","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/s00446-007-0021-5","volume":"19","author":"A. Pelc","year":"2007","unstructured":"A. Pelc. Activating anonymous ad hoc radio networks, Distributed Computing, 19:361\u2013371, 2007.","journal-title":"Distributed Computing"},{"key":"11_CR49","doi-asserted-by":"crossref","unstructured":"A. Pelc and D. Peleg. Feasibility and complexity of broadcasting with random transmission failures, In: Proceedings, 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM, Las Vegas, USA, pages 334\u2013341, 2005.","DOI":"10.1145\/1073814.1073879"},{"key":"11_CR50","doi-asserted-by":"crossref","unstructured":"D. Peleg. Time-efficient broadcasting in radio networks: A review, In: Proceedings, 4th International Conference on Distributed Computing and Internet Technology (ICDCIT), volume 4882 of Lecture Notes in Computer Science. Springer, Bangalore, India, pages 1\u201318, 2007.","DOI":"10.1007\/978-3-540-77115-9_1"},{"key":"11_CR51","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-3402-9","volume-title":"Multiple Access Protocols: Performance and Analysis","author":"R. Rom","year":"1990","unstructured":"R. Rom and M. Sidi. Multiple Access Protocols: Performance and Analysis, Springer, New York, NY, 1990."},{"key":"11_CR52","doi-asserted-by":"crossref","unstructured":"A. Ta-Shma, C. Umans, and D. Zuckerman. Loss-less condensers, unbalanced expanders, and extractors, In: Proceedings, 33rd ACM Symposium on Theory of Computing (STOC), ACM, Heraklion, Crete, Greece, pages 143\u2013152, 2001.","DOI":"10.1145\/380752.380790"},{"key":"11_CR53","first-page":"259","volume":"14","author":"B.S. Tsybakov","year":"1978","unstructured":"B.S. Tsybakov and V.A. Mikhailov. Free synchronous packet access in a broadcast channel with feedback, Prob Inf Transmission 14:259\u2013280, 1978. (Translated from Russian original in Problemy Peredachi Informatsii, 1977.)","journal-title":"Prob Inf Transmission"},{"key":"11_CR54","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1137\/0215032","volume":"15","author":"D.E. Willard","year":"1986","unstructured":"D.E. Willard. Log-logarithmic selection resolution protocols in a multiple access channel, SIAM Journal on Computing, 15:468\u2013477, 1986.","journal-title":"SIAM Journal on Computing"}],"container-title":["Monographs in Theoretical Computer Science. An EATCS Series","Theoretical Aspects of Distributed Computing in Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14849-1_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T08:36:47Z","timestamp":1741163807000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-14849-1_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,8]]},"ISBN":["9783642148484","9783642148491"],"references-count":54,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14849-1_11","relation":{},"ISSN":["1431-2654"],"issn-type":[{"type":"print","value":"1431-2654"}],"subject":[],"published":{"date-parts":[[2010,11,8]]},"assertion":[{"value":"8 November 2010","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}