Gossiping with bounded size messages in ad hoc radio networks (Extended abstract)
(2002) 29th International Colloquium, ICALP 2002 2380. p.377389 Abstract
 We study deterministic algorithms for the gossiping problem in ad hoc radio networks under the assumption that each combined message contains at most b(n) single messages or bits of auxiliary information, where b is an integer function and n is the number of nodes in the network. We term such a restricted gossiping problem b(n) gossiping. We show that rootngossiping in an ad hoc radio network on n nodes can be done deterministically in time (O) over tilde (n(3/2)) which asymptotically matches the best known upper bound on the time complexity of unrestricted deterministic gossiping(dagger). Our upper bound on rootngossiping is tight up to a polylogarithmic factor and it implies similarly tight upper bounds on b(n)gossiping where... (More)
 We study deterministic algorithms for the gossiping problem in ad hoc radio networks under the assumption that each combined message contains at most b(n) single messages or bits of auxiliary information, where b is an integer function and n is the number of nodes in the network. We term such a restricted gossiping problem b(n) gossiping. We show that rootngossiping in an ad hoc radio network on n nodes can be done deterministically in time (O) over tilde (n(3/2)) which asymptotically matches the best known upper bound on the time complexity of unrestricted deterministic gossiping(dagger). Our upper bound on rootngossiping is tight up to a polylogarithmic factor and it implies similarly tight upper bounds on b(n)gossiping where function b is computable and 1 less than or equal to b(n) : rootn holds. For symmetric ad hoc radio networks, we show that even 1gossiping can be done deterministically in time (O) over tilde (n(3/2)). We also demonstrate that O(n(t))gossiping in a symmetric ad hoc radio network on n nodes can be done in time O(n(2t)). Note that the latter upper bound is o(n(3/2)) when the size of a combined message is w(n(1/2)). Furthermore, by adopting known results on repeated randomized broadcasting in symmetric ad hoc radio networks, we derive a randomized protocol for 1gossiping in these networks running in time (O) over tilde (n) on the average. Finally, we observe that when a collision detection mechanism is available, even deterministic 1gossiping in symmetric ad hoc radio networks can be performed in time (O) over tilde (n). (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/321130
 author
 Christersson, M ; Gasieniec, L and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2002
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 Automata, Languages and Programming / Lecture Notes in Computer Science
 volume
 2380
 pages
 377  389
 publisher
 Springer
 conference name
 29th International Colloquium, ICALP 2002
 conference location
 Malaga, Spain
 conference dates
 20020708  20020713
 external identifiers

 wos:000180069500033
 scopus:84869193784
 ISSN
 16113349
 03029743
 DOI
 10.1007/3540454659_33
 language
 English
 LU publication?
 yes
 id
 56c24c4581e1494bb0ccbe7ae4ee44f5 (old id 321130)
 date added to LUP
 20160401 11:48:44
 date last changed
 20240603 21:11:05
@inproceedings{56c24c4581e1494bb0ccbe7ae4ee44f5, abstract = {{We study deterministic algorithms for the gossiping problem in ad hoc radio networks under the assumption that each combined message contains at most b(n) single messages or bits of auxiliary information, where b is an integer function and n is the number of nodes in the network. We term such a restricted gossiping problem b(n) gossiping. We show that rootngossiping in an ad hoc radio network on n nodes can be done deterministically in time (O) over tilde (n(3/2)) which asymptotically matches the best known upper bound on the time complexity of unrestricted deterministic gossiping(dagger). Our upper bound on rootngossiping is tight up to a polylogarithmic factor and it implies similarly tight upper bounds on b(n)gossiping where function b is computable and 1 less than or equal to b(n) : rootn holds. For symmetric ad hoc radio networks, we show that even 1gossiping can be done deterministically in time (O) over tilde (n(3/2)). We also demonstrate that O(n(t))gossiping in a symmetric ad hoc radio network on n nodes can be done in time O(n(2t)). Note that the latter upper bound is o(n(3/2)) when the size of a combined message is w(n(1/2)). Furthermore, by adopting known results on repeated randomized broadcasting in symmetric ad hoc radio networks, we derive a randomized protocol for 1gossiping in these networks running in time (O) over tilde (n) on the average. Finally, we observe that when a collision detection mechanism is available, even deterministic 1gossiping in symmetric ad hoc radio networks can be performed in time (O) over tilde (n).}}, author = {{Christersson, M and Gasieniec, L and Lingas, Andrzej}}, booktitle = {{Automata, Languages and Programming / Lecture Notes in Computer Science}}, issn = {{16113349}}, language = {{eng}}, pages = {{377389}}, publisher = {{Springer}}, title = {{Gossiping with bounded size messages in ad hoc radio networks (Extended abstract)}}, url = {{http://dx.doi.org/10.1007/3540454659_33}}, doi = {{10.1007/3540454659_33}}, volume = {{2380}}, year = {{2002}}, }