Advanced

On adaptive deterministic gossiping in ad hoc radio networks

Gasieniec, Leszek and Lingas, Andrzej LU (2002) In Information Processing Letters 83(2). p.89-93
Abstract
We study deterministic algorithms for gossiping problem in ad hoc radio networks. The efficiency of communication algorithms in radio networks is very often expressed in terms of: maximum eccentricity D, maximum in-degree Δ, and size (number of nodes) n of underlying graph of connections. The maximum eccentricity D of a network is the maximum of the lengths of shortest directed paths from a node u to a node v, taken over all ordered pairs (u,v) of nodes in the network. The maximum in-degree Δ of a network is the maximum of in-degrees of its nodes.We propose a new method that leads to several improvements in deterministic gossiping. It combines communication techniques designed for both known as well as unknown ad hoc... (More)
We study deterministic algorithms for gossiping problem in ad hoc radio networks. The efficiency of communication algorithms in radio networks is very often expressed in terms of: maximum eccentricity D, maximum in-degree &DELTA;, and size (number of nodes) n of underlying graph of connections. The maximum eccentricity D of a network is the maximum of the lengths of shortest directed paths from a node u to a node v, taken over all ordered pairs (u,v) of nodes in the network. The maximum in-degree &DELTA; of a network is the maximum of in-degrees of its nodes.We propose a new method that leads to several improvements in deterministic gossiping. It combines communication techniques designed for both known as well as unknown ad hoc radio networks. First we show how to subsume the O(Dn)-time bound yield by the round-robin procedure proposing a new O(Dn)-time gossiping algorithm.11Notation O(f(n)) stands for O(f(n). logcn), for any constant c>0. Our algorithm is more efficient than the known O(n3/2)-time gossiping algorithms [Proc. 41st IEEE Symp. on Found. of Computer Science, 2000, pp. 575-581; Proc. 13th ACM-SIAM Symp. on Discrete Algorithms, 2002], whenever D=O(nα) and α<1. For large values of maximum eccentricity D, we give another gossiping algorithm that works in time O(D&DELTA;3/2log3n) which subsumes the O(D&DELTA;2log3n) upper bound presented in [Proc. 20th ACM Symp. on Principles of Distributed Computing, 2001, pp. 255-263]. Finally, we observe that for any so-called oblivious (i.e., non-adaptive) deterministic gossiping algorithm, any natural n and 1=<D=<n-1, there is an unknown ad hoc radio network of size n and maximum eccentricity D which requires &OMEGA;(Dn) time-steps to complete gossiping. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Gossiping, Radio network, Distributed computing, Design of algorithms
in
Information Processing Letters
volume
83
issue
2
pages
89 - 93
publisher
Elsevier
external identifiers
  • wos:000175753800005
  • scopus:0037205804
ISSN
0020-0190
DOI
10.1016/S0020-0190(01)00312-X
language
English
LU publication?
yes
id
fa9afd59-2ae1-4b31-b04e-b0204247cd20 (old id 113733)
date added to LUP
2007-07-23 14:00:55
date last changed
2017-01-01 06:53:20
@article{fa9afd59-2ae1-4b31-b04e-b0204247cd20,
  abstract     = {We study deterministic algorithms for gossiping problem in ad hoc radio networks. The efficiency of communication algorithms in radio networks is very often expressed in terms of: maximum eccentricity D, maximum in-degree &amp;DELTA;, and size (number of nodes) n of underlying graph of connections. The maximum eccentricity D of a network is the maximum of the lengths of shortest directed paths from a node u to a node v, taken over all ordered pairs (u,v) of nodes in the network. The maximum in-degree &amp;DELTA; of a network is the maximum of in-degrees of its nodes.We propose a new method that leads to several improvements in deterministic gossiping. It combines communication techniques designed for both known as well as unknown ad hoc radio networks. First we show how to subsume the O(Dn)-time bound yield by the round-robin procedure proposing a new O(Dn)-time gossiping algorithm.11Notation O(f(n)) stands for O(f(n). logcn), for any constant c&gt;0. Our algorithm is more efficient than the known O(n3/2)-time gossiping algorithms [Proc. 41st IEEE Symp. on Found. of Computer Science, 2000, pp. 575-581; Proc. 13th ACM-SIAM Symp. on Discrete Algorithms, 2002], whenever D=O(nα) and α&lt;1. For large values of maximum eccentricity D, we give another gossiping algorithm that works in time O(D&amp;DELTA;3/2log3n) which subsumes the O(D&amp;DELTA;2log3n) upper bound presented in [Proc. 20th ACM Symp. on Principles of Distributed Computing, 2001, pp. 255-263]. Finally, we observe that for any so-called oblivious (i.e., non-adaptive) deterministic gossiping algorithm, any natural n and 1=&lt;D=&lt;n-1, there is an unknown ad hoc radio network of size n and maximum eccentricity D which requires &amp;OMEGA;(Dn) time-steps to complete gossiping.},
  author       = {Gasieniec, Leszek and Lingas, Andrzej},
  issn         = {0020-0190},
  keyword      = {Gossiping,Radio network,Distributed computing,Design of algorithms},
  language     = {eng},
  number       = {2},
  pages        = {89--93},
  publisher    = {Elsevier},
  series       = {Information Processing Letters},
  title        = {On adaptive deterministic gossiping in ad hoc radio networks},
  url          = {http://dx.doi.org/10.1016/S0020-0190(01)00312-X},
  volume       = {83},
  year         = {2002},
}