TY - GEN
T1 - Average-time complexity of gossiping in radio networks
AU - Chlebus, Bogdan S.
AU - Kowalski, Dariusz R.
AU - Rokicki, Mariusz A.
N1 - Copyright:
Copyright 2015 Elsevier B.V., All rights reserved.
PY - 2006
Y1 - 2006
N2 - Radio networks model wireless synchronous communication with only one wave frequency used for transmissions. In the problem of many-to-all (M2A) communication, some nodes hold input rumors, and the goal is to have all nodes learn all the rumors. We study the average time complexity of distributed many-to-all communication by deterministic protocols in directed networks under two scenarios: of combined messages, in which all input rumors can be sent in one packet, and of separate messages, in which every rumor requires a separate packet to be transmitted. Let n denote the size of a network and k be the number of nodes activated with rumors; the case when k = n is called gossiping. We give & gossiping protocol for combined messages that works in the average time script O sign(n/log n), which is shown to be optimal. For the general M2A communication problem, we show that it can be performed in the average time script O sign(min{k log(n/k),n/log n}) with combined messages, and that Ω(k/log n + log n) is a lower bound. We give a gossiping protocol for separate messages that works in the average time script O sign(n log n), which is shown to be optimal. For the general M2A communication problem, we develop a protocol for separate messages with the average time script O sign(k log(n/k) log n), and show that Ω(k log n) is a lower bound.
AB - Radio networks model wireless synchronous communication with only one wave frequency used for transmissions. In the problem of many-to-all (M2A) communication, some nodes hold input rumors, and the goal is to have all nodes learn all the rumors. We study the average time complexity of distributed many-to-all communication by deterministic protocols in directed networks under two scenarios: of combined messages, in which all input rumors can be sent in one packet, and of separate messages, in which every rumor requires a separate packet to be transmitted. Let n denote the size of a network and k be the number of nodes activated with rumors; the case when k = n is called gossiping. We give & gossiping protocol for combined messages that works in the average time script O sign(n/log n), which is shown to be optimal. For the general M2A communication problem, we show that it can be performed in the average time script O sign(min{k log(n/k),n/log n}) with combined messages, and that Ω(k/log n + log n) is a lower bound. We give a gossiping protocol for separate messages that works in the average time script O sign(n log n), which is shown to be optimal. For the general M2A communication problem, we develop a protocol for separate messages with the average time script O sign(k log(n/k) log n), and show that Ω(k log n) is a lower bound.
UR - http://www.scopus.com/inward/record.url?scp=33746382287&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33746382287&partnerID=8YFLogxK
U2 - 10.1007/11780823_20
DO - 10.1007/11780823_20
M3 - Conference contribution
AN - SCOPUS:33746382287
SN - 3540354743
SN - 9783540354741
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 253
EP - 267
BT - Structural Information and Communication Complexity - 13th International Colloquium, SIROCCO 2006, Proceedings
PB - Springer Verlag
T2 - 13th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2006
Y2 - 2 July 2006 through 5 July 2006
ER -