Advanced

Gossiping with bounded size messages in ad hoc radio networks (Extended abstract)

Christersson, M; Gasieniec, L and Lingas, Andrzej LU (2002) 29th International Colloquium, ICALP 2002 In Automata, Languages and Programming / Lecture Notes in Computer Science 2380. p.377-389
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 rootn-gossiping 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 rootn-gossiping is tight up to a poly-logarithmic 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 rootn-gossiping 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 rootn-gossiping is tight up to a poly-logarithmic 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 1-gossiping 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(2-t)). 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 1-gossiping 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 1-gossiping 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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Automata, Languages and Programming / Lecture Notes in Computer Science
volume
2380
pages
377 - 389
publisher
Springer
conference name
29th International Colloquium, ICALP 2002
external identifiers
  • wos:000180069500033
  • scopus:84869193784
ISSN
1611-3349
0302-9743
DOI
10.1007/3-540-45465-9_33
language
English
LU publication?
yes
id
56c24c45-81e1-494b-b0cc-be7ae4ee44f5 (old id 321130)
date added to LUP
2007-08-14 15:51:26
date last changed
2017-03-12 03:26:25
@inproceedings{56c24c45-81e1-494b-b0cc-be7ae4ee44f5,
  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 rootn-gossiping 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 rootn-gossiping is tight up to a poly-logarithmic 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 1-gossiping 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(2-t)). 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 1-gossiping 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 1-gossiping 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         = {1611-3349},
  language     = {eng},
  pages        = {377--389},
  publisher    = {Springer},
  title        = {Gossiping with bounded size messages in ad hoc radio networks (Extended abstract)},
  url          = {http://dx.doi.org/10.1007/3-540-45465-9_33},
  volume       = {2380},
  year         = {2002},
}