An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks

DOI10.1137/S0097539794279109zbMath0908.68067MaRDI QIDQ4388895

Yishay Mansour, Eyal Kushilevitz

Publication date: 10 May 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

lower boundsbroadcastradio networks

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Randomized algorithms (68W20) Network protocols (68M12) Distributed algorithms (68W15)

Related Items (65)

Distributed bare-bones communication in wireless networks ⋮ Performing work in broadcast networks ⋮ Broadcasting in UDG radio networks with missing and inaccurate information ⋮ Broadcasting in UDG radio networks with unknown topology ⋮ Centralized asynchronous broadcast in radio networks ⋮ Time efficient centralized gossiping in radio networks ⋮ Contention resolution in a non-synchronized multiple access channel ⋮ Tight bounds for FEC-based reliable multicast ⋮ Unbounded contention resolution in multiple-access channels ⋮ Quasi-optimal energy-efficient leader election algorithms in radio networks ⋮ Acknowledged broadcasting and gossiping in ad hoc radio networks ⋮ Leader election in ad hoc radio networks: a keen ear helps ⋮ Information gathering in ad-hoc radio networks with tree topology ⋮ Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election ⋮ Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony ⋮ Distributed multiple-message broadcast in wireless ad hoc networks under the SINR model ⋮ Distributed broadcast in radio networks of unknown topology. ⋮ Fast Radio Broadcasting with Advice ⋮ Dynamic multiple-message broadcast: bounding throughput in the affectance model ⋮ Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization ⋮ Scalable wake-up of multi-channel single-hop radio networks ⋮ Deterministic Communication in Radio Networks ⋮ Fast deterministic broadcast and gossiping algorithms for mobile ad hoc networks ⋮ Optimal deterministic broadcasting in known topology radio networks ⋮ Activating anonymous ad hoc radio networks ⋮ Broadcasting in geometric radio networks ⋮ Broadcasting in UDG Radio Networks with Missing and Inaccurate Information ⋮ Efficient Broadcasting in Known Geometric Radio Networks with Non-uniform Ranges ⋮ Deterministic broadcasting in ad hoc radio networks ⋮ Sensor Network Gossiping or How to Break the Broadcast Lower Bound ⋮ Coordination Problems in Ad Hoc Radio Networks ⋮ On the communication complexity of Bar-Yehuda, Goldreich and Itai's randomized broadcasting algorithm ⋮ Initializing sensor networks of non-uniform density in the weak sensor model ⋮ Faster information gathering in ad-hoc radio tree networks ⋮ Randomized mutual exclusion on a multiple access channel ⋮ Fast radio broadcasting with advice ⋮ Ordered and delayed adversaries and how to work against them on a shared channel ⋮ Improved lower bound for deterministic broadcasting in radio networks ⋮ Acknowledged broadcasting in ad hoc radio networks ⋮ Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism ⋮ Unnamed Item ⋮ The cost of global broadcast in dynamic radio networks ⋮ On simple back-off in unreliable radio networks ⋮ Efficient \(k\)-shot broadcasting in radio networks ⋮ Information exchange with collision detection on multiple channels ⋮ Broadcasting in undirected ad hoc radio networks ⋮ Information gathering in ad-hoc radio networks ⋮ CONTENTION RESOLUTION IN MULTIPLE-ACCESS CHANNELS: k-SELECTION IN RADIO NETWORKS ⋮ Broadcasting in dynamic radio networks ⋮ On the effect of the deployment setting on broadcasting in Euclidean radio networks ⋮ Many-to-many communication in radio networks ⋮ Local queuing under contention ⋮ Unbounded Contention Resolution in Multiple-Access Channels ⋮ Leveraging Channel Diversity to Gain Efficiency and Robustness for Wireless Broadcast ⋮ Energy efficient randomised communication in unknown AdHoc networks ⋮ Deterministic recurrent communication in restricted sensor networks ⋮ Asynchronous Broadcasting with Bivalent Beeps ⋮ Time-Efficient Broadcast in Radio Networks ⋮ On Efficient Gossiping in Radio Networks ⋮ Leader election in multi-hop radio networks ⋮ Exactly optimal deterministic radio broadcasting with collision detection ⋮ On adaptive deterministic gossiping in ad hoc radio networks. ⋮ The impact of information on broadcasting time in linear radio networks. ⋮ Noisy beeping networks ⋮ Faster broadcasting in unknown radio networks

This page was built for publication: An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks