Exactly optimal deterministic radio broadcasting with collision detection. (English) Zbl 07615860
Parter, Merav (ed.), Structural information and communication complexity. 29th international colloquium, SIROCCO 2022, Paderborn, Germany, June 27–29, 2022, Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13298, 234-252 (2022).
Summary: 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.
For the entire collection see [Zbl 1498.68015].
For the entire collection see [Zbl 1498.68015].
MSC:
| 68Mxx | Computer system organization |
| 68Q11 | Communication complexity, information complexity |
| 68R10 | Graph theory (including graph drawing) in computer science |
Software:
OEISReferences:
| [1] | Alon, N.; Bar-Noy, A.; Linial, N.; Peleg, D., A lower bound for radio broadcast, J. Comput. Syst. Sci., 43, 2, 290-298 (1991) · Zbl 0753.68006 · doi:10.1016/0022-0000(91)90015-W |
| [2] | 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) · Zbl 0752.68009 · doi:10.1016/0022-0000(92)90042-H |
| [3] | Bu, G.; Potop-Butucaru, M.; Rabie, M.; Georgiou, C.; Majumdar, R., Wireless broadcast with short labels, Networked Systems, 146-169 (2021), Cham: Springer, Cham · doi:10.1007/978-3-030-67087-0_10 |
| [4] | 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) · Zbl 1428.68061 |
| [5] | Chlamtac, I., The wave expansion approach to broadcasting in multihop radio networks, IEEE Trans. Commun., 39, 3, 426-433 (1991) · doi:10.1109/26.79285 |
| [6] | 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) · Zbl 1448.68084 · doi:10.1007/s446-002-8028-1 |
| [7] | Chlebus, BS; Gçasieniec, L.; Östlin, A.; Robson, JM; Montanari, U.; Rolim, JDP; Welzl, E., Deterministic radio broadcasting, Automata, Languages and Programming, 717-729 (2000), Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-45022-X_60 |
| [8] | Chrobak, M.; Gasieniec, L.; Rytter, W., Fast broadcasting and gossiping in radio networks, J. Algorithms, 43, 2, 177-189 (2002) · Zbl 1005.68009 · doi:10.1016/S0196-6774(02)00004-4 |
| [9] | Clementi, A.; Monti, A.; Silvestri, R., Distributed broadcast in radio networks of unknown topology, Theoret. Comput. Sci., 302, 1-3, 337-364 (2003) · Zbl 1051.90008 · doi:10.1016/S0304-3975(02)00851-4 |
| [10] | Cloitre, B.: The online encyclopedia of integer sequences (2002). http://oeis.org |
| [11] | Czumaj, A.; Davies, P., Deterministic communication in radio networks, SIAM J. Comput., 47, 1, 218-240 (2018) · Zbl 1387.68033 · doi:10.1137/17M1111322 |
| [12] | Czumaj, A.; Davies, P., Communicating with beeps, J. Parallel Distrib. Comput., 130, 98-109 (2019) · doi:10.1016/j.jpdc.2019.03.020 |
| [13] | Czumaj, A.; Rytter, W., Broadcasting algorithms in radio networks with unknown topology, J. Algorithms, 60, 2, 115-143 (2006) · Zbl 1100.68649 · doi:10.1016/j.jalgor.2004.08.001 |
| [14] | 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) |
| [15] | 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) · doi:10.1145/3470633 |
| [16] | 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) · Zbl 1421.68006 |
| [17] | Ghaffari, M.; Haeupler, B.; Khabbazian, M., Randomized broadcast in radio networks with collision detection, Distrib. Comput., 28, 6, 407-422 (2014) · Zbl 1348.68018 · doi:10.1007/s00446-014-0230-7 |
| [18] | Hounkanli, K., Pelc, A.: Deterministic broadcasting and gossiping with beeps. arXiv preprint arXiv:1508.06460 (2015) · Zbl 1482.68175 |
| [19] | Kowalski, D.; Pelc, A., Broadcasting in undirected ad hoc radio networks, Distrib. Comput., 18, 1, 43-57 (2005) · Zbl 1264.68218 · doi:10.1007/s00446-005-0126-7 |
| [20] | Kowalski, D.; Pelc, A., Optimal deterministic broadcasting in known topology radio networks, Distrib. Comput., 19, 3, 185-195 (2007) · Zbl 1266.68231 · doi:10.1007/s00446-006-0007-8 |
| [21] | 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) · Zbl 0908.68067 · doi:10.1137/S0097539794279109 |
| [22] | Nanah Ji, K.: Exactly optimal deterministic radio broadcasting with collision detection. arXiv preprint arXiv:2202.06375 (2022) |
| [23] | Pandita, N.: Ganita Kaumudi (1356) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
