TY - GEN
T1 - Gossiping with unit messages in known radio networks
AU - Gasieniec, Leszek
AU - Potapov, Igor
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2002
Y1 - 2002
N2 - A gossiping is a communication primitive in which each node of the network possesses a unique message that is to be communicated to all other nodes in the network. We study the gossiping problem in known ad hoc radio networks, where during each transmission only unit messages originated at any node of the network can be transmitted successfully. We survey a number of radio network topologies. Assuming that the size (a number of nodes) of the network is n we show that the exact complexity of radio gossiping in stars is 2n-1, in rings is 2n±O(l), and on a line of processors is 3n ± O(1). We later prove that radio gossiping in free trees is harder and it requires at least 3 1/6 n - 16 time steps to be completed. For free trees we also show a gossiping algorithm with time complexity 5n + 8. In conclusion we prove that in general graphs radio gossiping requires ω(n log n) time, and we propose radio gossiping algorithm that works in time O(n log2 n).
AB - A gossiping is a communication primitive in which each node of the network possesses a unique message that is to be communicated to all other nodes in the network. We study the gossiping problem in known ad hoc radio networks, where during each transmission only unit messages originated at any node of the network can be transmitted successfully. We survey a number of radio network topologies. Assuming that the size (a number of nodes) of the network is n we show that the exact complexity of radio gossiping in stars is 2n-1, in rings is 2n±O(l), and on a line of processors is 3n ± O(1). We later prove that radio gossiping in free trees is harder and it requires at least 3 1/6 n - 16 time steps to be completed. For free trees we also show a gossiping algorithm with time complexity 5n + 8. In conclusion we prove that in general graphs radio gossiping requires ω(n log n) time, and we propose radio gossiping algorithm that works in time O(n log2 n).
UR - http://www.scopus.com/inward/record.url?scp=84891098644&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84891098644&partnerID=8YFLogxK
U2 - 10.1007/978-0-387-35608-2_17
DO - 10.1007/978-0-387-35608-2_17
M3 - Conference contribution
AN - SCOPUS:84891098644
SN - 9781475752755
T3 - IFIP Advances in Information and Communication Technology
SP - 193
EP - 205
BT - Foundations of Information Technology in the Era of Network and Mobile Computing - IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP Int. Conference on Theoretical Computer Science (TCS 2002)
PB - Springer New York LLC
T2 - IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science, TCS 2002
Y2 - 25 August 2002 through 30 August 2002
ER -