{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T00:44:58Z","timestamp":1791074698763,"version":"4.1.0"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We show that for any randomized broadcast protocol for radio networks, there exists a network in which the expected time to broadcast a message is $\\Omega(D\\log (N\/D))$, where D is the diameter of the network and N is the number of nodes. This implies a tight lower bound of $\\Omega(D\\log N)$ for any $D \\le N^{1-\\varepsilon}$, where $\\varepsilon &gt; 0$ is any constant.<\/jats:p>","DOI":"10.1137\/s0097539794279109","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"702-712","source":"Crossref","is-referenced-by-count":206,"title":["An $\\Omega(D\\log (N\/D))$ Lower Bound for Broadcast in Radio Networks"],"prefix":"10.1137","volume":"27","author":[{"given":"Eyal","family":"Kushilevitz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90015-W"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90015-5"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02259748"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90042-H"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0222055"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1985.1096245"},{"key":"R7","unstructured":"I. Chlamtac and S. Kutten,\n                      A spatial reuse TDMA\/FDMA for mobile multi\u2010hop radio networks\n                      , in INFOCOM, 1985, pp. 389\u2013394."},{"key":"R8","first-page":"1209","volume":"36","author":"Chlamtac I.","year":"1987","journal-title":"IEEECOM"},{"key":"R9","unstructured":"I. Chlamtac and O. Weinstein,\n                      The wave expansion approach to broadcasting in multihop radio networks\n                      , in INFOCOM, pp. 874\u2013881, 1987."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1985.1057022"},{"key":"R11","unstructured":"I. Gaber and Y. Mansour,\n                      Broadcast in radio networks\n                      , in Proc. 6th ACM\u2010SIAM Symposium on Discrete Algorithms, SIAM, 1995, pp. 577\u2013585."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and Y. Mansour,\n                      An \u03a9(Dlog(N\/D)) lower bound for broadcast in radio networks\n                      , in Proc. 12th ACM Symp. on Principles of Distributed Computing, 1993, pp. 65\u201374.","DOI":"10.1145\/164051.164059"},{"key":"R13","unstructured":"A. S. Tanenbaum,\n                      Computer Networks\n                      , Prentice\u2010Hall, Englewood Cliffs, NJ, 1981."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0215032"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794279109","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:37Z","timestamp":1787336017000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794279109"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794279109"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794279109","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}