Fast radio broadcasting with advice

被引:0
作者
Ilcinkas, David [1 ]
Kowalski, Dariusz R. [2 ]
Pelc, Andrzej [3 ]
机构
[1] Univ Bordeaux 1, CNRS, LaBRI, F-33405 Talence, France
[2] Univ Liverpool, Dept Comp Sci, Liverpool L69 3BX, Merseyside, England
[3] Univ Quebec, Ste Foy, PQ G1V 2M3, Canada
来源
STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY | 2008年 / 5058卷
基金
加拿大自然科学与工程研究理事会;
关键词
radio network; distributed algorithm; deterministic broadcasting; advice;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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.
引用
收藏
页码:291 / +
页数:3
相关论文
共 30 条
[1]   A LOWER BOUND FOR RADIO BROADCAST [J].
ALON, N ;
BARNOY, A ;
LINIAL, N ;
PELEG, D .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1991, 43 (02) :290-298
[2]  
[Anonymous], 2005, P 24 ANN S PRINC DIS
[3]   ON THE TIME-COMPLEXITY OF BROADCAST IN MULTIHOP RADIO NETWORKS - AN EXPONENTIAL GAP BETWEEN DETERMINISM AND RANDOMIZATION [J].
BARYEHUDA, R ;
GOLDREICH, O ;
ITAI, A .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1992, 45 (01) :104-126
[4]  
Brito C, 2004, LECT NOTES COMPUT SC, V2996, P534
[5]   Lower bounds for the broadcast problem in mobile radio networks [J].
Bruschi, D ;
DelPinto, M .
DISTRIBUTED COMPUTING, 1997, 10 (03) :129-135
[6]   THE WAVE EXPANSION APPROACH TO BROADCASTING IN MULTIHOP RADIO NETWORKS [J].
CHLAMTAC, I ;
WEINSTEIN, O .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1991, 39 (03) :426-433
[7]   ON BROADCASTING IN RADIO NETWORKS - PROBLEM ANALYSIS AND PROTOCOL DESIGN [J].
CHLAMTAC, I ;
KUTTEN, S .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1985, 33 (12) :1240-1246
[8]   Deterministic broadcasting in ad hoc radio networks [J].
Chlebus, BS ;
Gasieniec, L ;
Gibbons, A ;
Pelc, A ;
Rytter, W .
DISTRIBUTED COMPUTING, 2002, 15 (01) :27-38
[9]  
Chlebus BS, 2000, LECT NOTES COMPUT SC, V1853, P717
[10]  
CHROBAK M, 2004, P 15 ACM SIAM S DISC, P985