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 -