Abstract
We consider the broadcast problem in synchronous radio broadcast models with collision detection. One node of the network is given a message that must be learned by all nodes in the network. We provide a deterministic algorithm that works on the beeping model, which is a restricted version of the radio broadcast model with collision detection. This algorithm improves on the round complexity of previous algorithms. We prove an exactly matching lower bound in the radio broadcast model with collision detection. This shows that the extra power provided by the radio broadcast model with collision detection does not help improve the round complexity.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A lower bound for radio broadcast. J. Comput. Syst. Sci. 43(2), 290–298 (1991)
Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. J. Comput. Syst. Sci. 45(1), 104–126 (1992)
Bu, G., Potop-Butucaru, M., Rabie, M.: Wireless broadcast with short labels. In: Georgiou, C., Majumdar, R. (eds.) NETYS 2020. LNCS, vol. 12129, pp. 146–169. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-67087-0_10
Chang, Y.J., Dani, V., Hayes, T.P., He, Q., Li, W., Pettie, S.: The energy complexity of broadcast. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pp. 95–104 (2018)
Chlamtac, I.: The wave expansion approach to broadcasting in multihop radio networks. IEEE Trans. Commun. 39(3), 426–433 (1991)
Chlebus, B., Gąsieniec, L., Gibbons, A., Pelc, A., Rytter, W.: Deterministic broadcasting in ad hoc radio networks. Distrib. Comput. 15(1), 27–38 (2002)
Chlebus, B.S., Gçasieniec, L., Östlin, A., Robson, J.M.: Deterministic radio broadcasting. In: Montanari, U., Rolim, J.D.P., Welzl, E. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 717–729. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45022-X_60
Chrobak, M., Gasieniec, L., Rytter, W.: Fast broadcasting and gossiping in radio networks. J. Algorithms 43(2), 177–189 (2002)
Clementi, A., Monti, A., Silvestri, R.: Distributed broadcast in radio networks of unknown topology. Theoret. Comput. Sci. 302(1–3), 337–364 (2003)
Cloitre, B.: The online encyclopedia of integer sequences (2002). http://oeis.org
Czumaj, A., Davies, P.: Deterministic communication in radio networks. SIAM J. Comput. 47(1), 218–240 (2018)
Czumaj, A., Davies, P.: Communicating with beeps. J. Parallel Distrib. Comput. 130, 98–109 (2019)
Czumaj, A., Rytter, W.: Broadcasting algorithms in radio networks with unknown topology. J. Algorithms 60(2), 115–143 (2006)
Ellen, F., Gilbert, S.: Constant-length labelling schemes for faster deterministic radio broadcast. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 213–222 (2020)
Ellen, F., Gorain, B., Miller, A., Pelc, A.: Constant-length labeling schemes for deterministic radio broadcast. ACM Trans. Parallel Comput. 8(3), 1–17 (2021)
Ghaffari, M., Haeupler, B.: Near optimal leader election in multi-hop radio networks. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 748–766. SIAM (2013)
Ghaffari, M., Haeupler, B., Khabbazian, M.: Randomized broadcast in radio networks with collision detection. Distrib. Comput. 28(6), 407–422 (2014). https://doi.org/10.1007/s00446-014-0230-7
Hounkanli, K., Pelc, A.: Deterministic broadcasting and gossiping with beeps. arXiv preprint arXiv:1508.06460 (2015)
Kowalski, D., Pelc, A.: Broadcasting in undirected ad hoc radio networks. Distrib. Comput. 18(1), 43–57 (2005)
Kowalski, D., Pelc, A.: Optimal deterministic broadcasting in known topology radio networks. Distrib. Comput. 19(3), 185–195 (2007)
Kushilevitz, E., Mansour, Y.: An \(\omega (d \cdot \log {\frac{n}{d}})\) lower bound for broadcast in radio networks. SIAM J. Comput. 27(3), 702–712 (1998)
Nanah Ji, K.: Exactly optimal deterministic radio broadcasting with collision detection. arXiv preprint arXiv:2202.06375 (2022)
Pandita, N.: Ganita Kaumudi (1356)
Acknowledgments
I would like thank my supervisor, Faith Ellen, for her patience and support throughout this project. Her insightful feedback and guidance brought my work to a much higher level. I would also like to thank the anonymous reviewers for their time and helpful comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Nanahji, K. (2022). Exactly Optimal Deterministic Radio Broadcasting with Collision Detection. In: Parter, M. (eds) Structural Information and Communication Complexity. SIROCCO 2022. Lecture Notes in Computer Science, vol 13298. Springer, Cham. https://doi.org/10.1007/978-3-031-09993-9_13
Download citation
DOI: https://doi.org/10.1007/978-3-031-09993-9_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-09992-2
Online ISBN: 978-3-031-09993-9
eBook Packages: Computer ScienceComputer Science (R0)