# Average-Time Complexity of Gossiping in Radio Networks

• Bogdan S. Chlebus
• Dariusz R. Kowalski
• Mariusz A. Rokicki
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)

## Abstract

Radio networks model wireless synchronous communication with only one wave frequency used for transmissions. In the problem of many-to-all (M2A) communication, some nodes hold input rumors, and the goal is to have all nodes learn all the rumors. We study the average time complexity of distributed many-to-all communication by deterministic protocols in directed networks under two scenarios: of combined messages, in which all input rumors can be sent in one packet, and of separate messages, in which every rumor requires a separate packet to be transmitted. Let n denote the size of a network and k be the number of nodes activated with rumors; the case when k = n is called gossiping. We give a gossiping protocol for combined messages that works in the average time $${\mathcal O}(n/\log n)$$, which is shown to be optimal. For the general M2A communication problem, we show that it can be performed in the average time $${\mathcal O}(\min\{k\log(n/k),n/\log n\})$$ with combined messages, and that Ω(k/logn + logn) is a lower bound. We give a gossiping protocol for separate messages that works in the average time $${\mathcal O}(n\log n)$$, which is shown to be optimal. For the general M2A communication problem, we develop a protocol for separate messages with the average time $${\mathcal O}(k\log(n/k)\log n)$$, and show that Ω(k logn) is a lower bound.

## Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

## References

1. 1.
Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A lower bound for radio broadcast. Journal of Computer and System Sciences 43, 290–298 (1991)
2. 2.
Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time complexity of broadcast in radio networks: An exponential gap between determinism and randomization. J. Computer and System Sciences 45, 104–126 (1992)
3. 3.
Bar-Yehuda, R., Israeli, A., Itai, A.: Multiple communication in multi-hop radio networks. SIAM J. on Computing 22, 875–887 (1993)
4. 4.
Chlamtac, I., Kutten, S.: On broadcasting in radio networks - problem analysis and protocol design. IEEE Transactions on Communication 33, 1240–1246 (1985)
5. 5.
Chlebus, B.S., Gąsieniec, L., Gibbons, A.M., Pelc, A., Rytter, W.: Deterministic broadcasting in ad hoc radio networks. Distributed Computing 15, 27–38 (2002)
6. 6.
Chlebus, B.S., Gąsieniec, L., Lingas, A., Pagourtzis, A.: Oblivious gossiping in ad-hoc radio networks. In: Proc. 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pp. 44–51 (2001)Google Scholar
7. 7.
Christersson, M., Gąsieniec, L., Lingas, A.: Gossiping with bounded size messages in ad hoc radio networks. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 377–389. Springer, Heidelberg (2002)
8. 8.
Chrobak, M., Gąsieniec, L., Rytter, W.: Fast broadcasting and gossiping in radio networks. Journal of Algorithms 43, 177–189 (2002)
9. 9.
Clementi, A.E.F., Monti, A., Silvestri, R.: Distributed broadcasting in radio networks of unknown topology. Theoretical Computer Science 302, 337–364 (2003)
10. 10.
Czumaj, A., Rytter, W.: Broadcasting algorithms in radio networks with unknown topology. In: Proc. 44th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 492–501 (2003)Google Scholar
11. 11.
De Bonis, A., Gąsieniec, L., Vaccaro, U.: Generalized framework for selectors with applications in optimal group testing. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 81–96. Springer, Heidelberg (2003)
12. 12.
Elsässer, R., Gąsieniec, L.: Radio communication in random graphs. In: Proc. 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 309–315 (2005)Google Scholar
13. 13.
Ga̧sieniec, L., Kranakis, E., Pelc, A., Xin, Q.: Deterministic M2M multicast in radio networks. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 670–682. Springer, Heidelberg (2004)
14. 14.
Gąsieniec, L., Radzik, T., Xin, Q.: Faster deterministic gossiping in directed ad hoc radio networks. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 397–407. Springer, Heidelberg (2004)
15. 15.
Kowalski, D.R., Pelc, A.: Time of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism. In: Proc. 10th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 195–210 (2003)Google Scholar

## Authors and Affiliations

• Bogdan S. Chlebus
• 1
• Dariusz R. Kowalski
• 2
• Mariusz A. Rokicki
• 1
1. 1.Department of Computer Science and Eng.UCDHSCDenverUSA
2. 2.Department of Computer ScienceUniversity of LiverpoolLiverpoolUK