{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T07:21:02Z","timestamp":1772608862495,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,9,20]],"date-time":"2021-09-20T00:00:00Z","timestamp":1632096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Natural Sciences and Engineering Research Council of Canada (NSERC), Discovery","award":["RGPIN\u20132015\u201305080, RGPIN\u20132020\u201304178, RGPIN\u20132017\u201305936 and RGPIN\u20132018\u201303899"],"award-info":[{"award-number":["RGPIN\u20132015\u201305080, RGPIN\u20132020\u201304178, RGPIN\u20132017\u201305936 and RGPIN\u20132018\u201303899"]}]},{"name":"Research Chair in Distributed Computing at the Universit\u00e9 du Qu\u00e9bec en Outaouais"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>\n            Broadcast is one of the fundamental network communication primitives. One node of a network, called the\n            <jats:italic>s<\/jats:italic>\n            ource, has a message that has to be learned by all other nodes. We consider broadcast in radio networks, modeled as simple undirected connected graphs with a distinguished source. Nodes communicate in synchronous rounds. In each round, a node can either transmit a message to all its neighbours, or stay silent and listen. At the receiving end, a node\n            <jats:italic>v<\/jats:italic>\n            hears a message from a neighbour\n            <jats:italic>w<\/jats:italic>\n            in a given round if\n            <jats:italic>v<\/jats:italic>\n            listens in this round and if\n            <jats:italic>w<\/jats:italic>\n            is its only neighbour that transmits in this round. If more than one neighbour of a node\n            <jats:italic>v<\/jats:italic>\n            transmits in a given round, we say that a\n            <jats:italic>c<\/jats:italic>\n            ollision occurs at\n            <jats:italic>v<\/jats:italic>\n            . We do not assume collision detection: in case of a collision, node\n            <jats:italic>v<\/jats:italic>\n            does not hear anything (except the background noise that it also hears when no neighbour transmits).\n          <\/jats:p>\n          <jats:p>\n            We are interested in the feasibility of deterministic broadcast in radio networks. If nodes of the network do not have any labels, deterministic broadcast is impossible even in the four-cycle. On the other hand, if all nodes have distinct labels, then broadcast can be carried out, e.g., in a round-robin fashion, and hence\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            )-bit labels are sufficient for this task in\n            <jats:italic>n<\/jats:italic>\n            -node networks. In fact,\n            <jats:italic>O<\/jats:italic>\n            (log \u0394)-bit labels, where \u0394 is the maximum degree, are enough to broadcast successfully. Hence, it is natural to ask if very short labels are sufficient for broadcast. Our main result is a positive answer to this question. We show that every radio network can be labeled using 2 bits in such a way that broadcast can be accomplished by some universal deterministic algorithm that does not know the network topology nor any bound on its size. Moreover, at the expense of an extra bit in the labels, we can get the following additional strong property of our algorithm: there exists a common round in which all nodes know that broadcast has been completed. Finally, we show that 3-bit labels are also sufficient to solve both versions of broadcast in the case where it is not known\n            <jats:italic>a priori<\/jats:italic>\n            which node is the source.\n          <\/jats:p>","DOI":"10.1145\/3470633","type":"journal-article","created":{"date-parts":[[2021,9,20]],"date-time":"2021-09-20T18:27:58Z","timestamp":1632162478000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Constant-Length Labeling Schemes for Deterministic Radio Broadcast"],"prefix":"10.1145","volume":"8","author":[{"given":"Faith","family":"Ellen","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Toronto, Toronto, Ontario, Canada"}]},{"given":"Barun","family":"Gorain","sequence":"additional","affiliation":[{"name":"Electrical Engineering and Computer Science, Indian Institute of Information Technology Bhilai, Sejbahar, Chhattisgarh, India"}]},{"given":"Avery","family":"Miller","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Manitoba, Winnipeg, Manitoba, Canada"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[{"name":"D\u00e9partement d\u2019informatique et d\u2019ing \u00e9 nierie, Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau, Qu\u00e9bec, Canada"}]}],"member":"320","published-online":{"date-parts":[[2021,9,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703437211"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90015-W"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/171540.171571"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004460050030"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 8th International Conference on Networked Systems (NETYS\u201920)","volume":"12129","author":"Bu Gewu","year":"2020","unstructured":"Gewu Bu , Maria Potop-Butucaru , and Mika\u00ebl Rabie . 2020 . Wireless broadcast with short labels . In Proceedings of the 8th International Conference on Networked Systems (NETYS\u201920) . Lecture Notes in Computer Science (LNCS) , vol. 12129 , Springer. Gewu Bu, Maria Potop-Butucaru, and Mika\u00ebl Rabie. 2020. Wireless broadcast with short labels. In Proceedings of the 8th International Conference on Networked Systems (NETYS\u201920). Lecture Notes in Computer Science (LNCS), vol. 12129, Springer."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1985.1096245"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 7th International Conference on Distributed Computing Systems","author":"Chlamtac Imrich","year":"1987","unstructured":"Imrich Chlamtac and O. Weinstein . 1987. Distributed \u201dWave\u201d broadcasting in mobil multi-hop radio networks . In Proceedings of the 7th International Conference on Distributed Computing Systems ( Berlin, Germany , September 1987 ). IEEE Computer Society, 82\u201389. Imrich Chlamtac and O. Weinstein. 1987. Distributed \u201dWave\u201d broadcasting in mobil multi-hop radio networks. In Proceedings of the 7th International Conference on Distributed Computing Systems(Berlin, Germany, September 1987). IEEE Computer Society, 82\u201389."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s446-002-8028-1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/646253.686345"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00004-4"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00851-4"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1383369.1383373"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, (ICALP\u201916)","volume":"55","author":"Czumaj Artur","year":"2016","unstructured":"Artur Czumaj and Peter Davies . 2016 . Faster deterministic communication in radio networks . In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, (ICALP\u201916) , (July 11-15, 2016, Rome, Italy) (LIPIcs), Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (Eds.) , Vol. 55 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 139:1\u2013139:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.139 10.4230\/LIPIcs.ICALP.2016.139 Artur Czumaj and Peter Davies. 2016. Faster deterministic communication in radio networks. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, (ICALP\u201916), (July 11-15, 2016, Rome, Italy) (LIPIcs), Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (Eds.), Vol. 55. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 139:1\u2013139:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.139"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.08.001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2011.10.004"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186810.1186818"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400238"},{"key":"e_1_2_1_18_1","volume-title":"Constant-length labeling schemes for deterministic radio broadcast. CoRR abs\/1710.03178","author":"Ellen Faith","year":"2017","unstructured":"Faith Ellen , Barun Gorain , Avery Miller , and Andrzej Pelc . 2017. Constant-length labeling schemes for deterministic radio broadcast. CoRR abs\/1710.03178 ( 2017 ). arxiv:1710.03178http:\/\/arxiv.org\/abs\/1710.03178 Faith Ellen, Barun Gorain, Avery Miller, and Andrzej Pelc. 2017. Constant-length labeling schemes for deterministic radio broadcast. CoRR abs\/1710.03178 (2017). arxiv:1710.03178http:\/\/arxiv.org\/abs\/1710.03178"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.007"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-008-0076-y"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.07.005"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.07.002"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9280-9"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2016.01.005"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00292-4"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118733.3118819"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-006-0011-z"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.03.059"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.05.002"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3039870"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-72050-0_3"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154273.3154298"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.01.004"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703433912"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0095-3"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0126-7"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.04.017"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-006-0007-8"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.04.003"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279109"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.020"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470633","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470633","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:55Z","timestamp":1750191535000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470633"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,20]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3470633"],"URL":"https:\/\/doi.org\/10.1145\/3470633","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,20]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}