TY - GEN
T1 - Fast radio broadcasting with advice
AU - Ilcinkas, David
AU - Kowalski, Dariusz R.
AU - Pelc, Andrzej
N1 - Funding Information:
This work was done during the stay of David Ilcinkas at the Research Chair in Distributed Computing of the Université du Québec en Outaouais and at the University of Ottawa, as a postdoctoral fellow. First author’s research partially supported by the ANR project ‘‘ALADDIN’’, and the INRIA project ‘‘CEPAGE’’. Second author’s work was supported by the Engineering and Physical Sciences Research Council [grant number EP/G023018/1]. Third author’s research partially supported by NSERC discovery grant and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais.
PY - 2008
Y1 - 2008
N2 - We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with advice. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and the time in which broadcasting can be accomplished. In particular, we ask what is the minimum number of bits of information that must be available to nodes of the network, in order to broadcast very fast. For networks in which constant time broadcast is possible under complete knowledge of the network we give a tight answer to the above question: O(n) bits of advice are sufficient but o(n) bits are not, in order to achieve constant broadcasting time in all these networks. This is in sharp contrast with geometric radio networks of constant broadcasting time: we show that in these networks a constant number of bits suffices to broadcast in constant time. For arbitrary radio networks we present a broadcasting algorithm whose time is inverse-proportional to the size of advice.
AB - We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with advice. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and the time in which broadcasting can be accomplished. In particular, we ask what is the minimum number of bits of information that must be available to nodes of the network, in order to broadcast very fast. For networks in which constant time broadcast is possible under complete knowledge of the network we give a tight answer to the above question: O(n) bits of advice are sufficient but o(n) bits are not, in order to achieve constant broadcasting time in all these networks. This is in sharp contrast with geometric radio networks of constant broadcasting time: we show that in these networks a constant number of bits suffices to broadcast in constant time. For arbitrary radio networks we present a broadcasting algorithm whose time is inverse-proportional to the size of advice.
KW - Advice
KW - Deterministic broadcasting
KW - Distributed algorithm
KW - Radio network
UR - http://www.scopus.com/inward/record.url?scp=48249094973&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=48249094973&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-69355-0_24
DO - 10.1007/978-3-540-69355-0_24
M3 - Conference contribution
AN - SCOPUS:48249094973
SN - 3540693262
SN - 9783540693260
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 291
EP - 305
BT - Structural Information and Communication Complexity - 15th International Colloquium, SIROCCO 2008, Proceedings
T2 - 15th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2008
Y2 - 17 June 2008 through 20 June 2008
ER -