On adaptive deterministic gossiping in ad hoc radio networks
(2002) Symposium on Discrete Algorithms, 2002 p.689690 Abstract
 We study deterministic algorithms for gossiping problem in ad hoc radio networks. The gossiping problem is a communication task in which each node of the network possesses a unique single message that is to be communicated to all other nodes in the network. The efficiency of a communication algorithm in radio networks is very often expressed in terms of: maxeccentricity D, maxindegree Δ, and size (number of nodes) n of underlying graph of connections. The maxeccentricity 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 maxindegree Δ of a network is the maximum of indegrees of its nodes.We propose a new method that leads to... (More)
 We study deterministic algorithms for gossiping problem in ad hoc radio networks. The gossiping problem is a communication task in which each node of the network possesses a unique single message that is to be communicated to all other nodes in the network. The efficiency of a communication algorithm in radio networks is very often expressed in terms of: maxeccentricity D, maxindegree Δ, and size (number of nodes) n of underlying graph of connections. The maxeccentricity 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 maxindegree Δ 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 Õ(√Dn)time gossiping algorithm. Our algorithm is more efficient than the known Õ(n3/2)time gossiping algorithms [3, 6], whenever D = O(nα) and α < 1. For large values of maxeccentricity D, we give another gossiping algorithm that works in time O(DΔ3/2 log3 n) which subsumes the O(DΔ2 log3 n) upper bound presented in [4]. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/631639
 author
 Gasieniec, Leszek and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2002
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 Proceedings of the thirteenth annual ACMSIAM symposium on Discrete algorithms
 pages
 689  690
 publisher
 Society for Industrial and Applied Mathematics
 conference name
 Symposium on Discrete Algorithms, 2002
 conference location
 San Francisco, California, United States
 conference dates
 20020106  20020108
 external identifiers

 scopus:0037205804
 ISBN
 089871513X
 language
 English
 LU publication?
 yes
 id
 44dedb697d3f4dee86b4ee1870b89fe7 (old id 631639)
 alternative location
 http://portal.acm.org/citation.cfm?id=545473&coll=GUIDE&dl=GUIDE&CFID=44876763&CFTOKEN=37550423
 date added to LUP
 20160404 10:12:50
 date last changed
 20201208 03:09:42
@inproceedings{44dedb697d3f4dee86b4ee1870b89fe7, abstract = {We study deterministic algorithms for gossiping problem in ad hoc radio networks. The gossiping problem is a communication task in which each node of the network possesses a unique single message that is to be communicated to all other nodes in the network. The efficiency of a communication algorithm in radio networks is very often expressed in terms of: maxeccentricity D, maxindegree Δ, and size (number of nodes) n of underlying graph of connections. The maxeccentricity 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 maxindegree Δ 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 Õ(√Dn)time gossiping algorithm. Our algorithm is more efficient than the known Õ(n3/2)time gossiping algorithms [3, 6], whenever D = O(nα) and α < 1. For large values of maxeccentricity D, we give another gossiping algorithm that works in time O(DΔ3/2 log3 n) which subsumes the O(DΔ2 log3 n) upper bound presented in [4].}, author = {Gasieniec, Leszek and Lingas, Andrzej}, booktitle = {Proceedings of the thirteenth annual ACMSIAM symposium on Discrete algorithms}, isbn = {089871513X}, language = {eng}, pages = {689690}, publisher = {Society for Industrial and Applied Mathematics}, title = {On adaptive deterministic gossiping in ad hoc radio networks}, url = {http://portal.acm.org/citation.cfm?id=545473&coll=GUIDE&dl=GUIDE&CFID=44876763&CFTOKEN=37550423}, year = {2002}, }