On adaptive deterministic gossiping in ad hoc radio networks
(2002) In Information Processing Letters 83(2). p.8993 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 indegree &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 indegree &DELTA; of a network is the maximum of indegrees 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 indegree &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 indegree &DELTA; of a network is the maximum of indegrees 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 roundrobin 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. 575581; Proc. 13th ACMSIAM 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. 255263]. Finally, we observe that for any socalled oblivious (i.e., nonadaptive) deterministic gossiping algorithm, any natural n and 1=<D=<n1, there is an unknown ad hoc radio network of size n and maximum eccentricity D which requires &OMEGA;(Dn) timesteps to complete gossiping. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/113733
 author
 Gasieniec, Leszek and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2002
 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
 00200190
 DOI
 10.1016/S00200190(01)00312X
 language
 English
 LU publication?
 yes
 id
 fa9afd592ae14b31b04eb0204247cd20 (old id 113733)
 date added to LUP
 20070723 14:00:55
 date last changed
 20170101 06:53:20
@article{fa9afd592ae14b31b04eb0204247cd20, 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 indegree &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 indegree &DELTA; of a network is the maximum of indegrees 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 roundrobin 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. 575581; Proc. 13th ACMSIAM 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. 255263]. Finally, we observe that for any socalled oblivious (i.e., nonadaptive) deterministic gossiping algorithm, any natural n and 1=<D=<n1, there is an unknown ad hoc radio network of size n and maximum eccentricity D which requires &OMEGA;(Dn) timesteps to complete gossiping.}, author = {Gasieniec, Leszek and Lingas, Andrzej}, issn = {00200190}, keyword = {Gossiping,Radio network,Distributed computing,Design of algorithms}, language = {eng}, number = {2}, pages = {8993}, publisher = {Elsevier}, series = {Information Processing Letters}, title = {On adaptive deterministic gossiping in ad hoc radio networks}, url = {http://dx.doi.org/10.1016/S00200190(01)00312X}, volume = {83}, year = {2002}, }