On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
From MaRDI portal
Publication:1198663
DOI10.1016/0022-0000(92)90042-HzbMath0752.68009MaRDI QIDQ1198663
Oded Goldreich, Alon Itai, Reuven Bar Yehuda
Publication date: 16 January 1993
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10)
Related Items (only showing first 100 items - show all)
The minimum broadcast range assignment problem on linear multi-hop wireless networks. ⋮ Optimal gossiping in geometric radio networks in the presence of dynamical faults ⋮ Broadcasting with locally bounded byzantine faults ⋮ Generalized framework for group testing: queries, feedbacks and adversaries ⋮ On Conflict-Free Multi-coloring ⋮ Fast message dissemination in random geometric networks ⋮ Broadcasting in UDG radio networks with missing and inaccurate information ⋮ Coloring unstructured radio networks ⋮ Broadcasting in UDG radio networks with unknown topology ⋮ Energy-Optimal Broadcast in a Tree with Mobile Agents ⋮ The time complexity of deterministic broadcast radio networks ⋮ Centralized asynchronous broadcast in radio networks ⋮ Time efficient centralized gossiping in radio networks ⋮ Upper and lower bounds for deterministic broadcast in powerline communication networks ⋮ Modeling Radio Networks ⋮ The parameterized complexity of unique coverage and its variants ⋮ Time efficient \(k\)-shot broadcasting in known topology radio networks ⋮ Feasibility and complexity of broadcasting with random transmission failures ⋮ Unbounded contention resolution in multiple-access channels ⋮ Quasi-optimal energy-efficient leader election algorithms in radio networks ⋮ Information dissemination in unknown radio networks with large labels ⋮ Leader election in ad hoc radio networks: a keen ear helps ⋮ Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony ⋮ Deterministic broadcasting time with partial knowledge of the network. ⋮ Distributed broadcast in radio networks of unknown topology. ⋮ The distributed wireless gathering problem ⋮ Fast Radio Broadcasting with Advice ⋮ The Distributed Wireless Gathering Problem ⋮ Randomized broadcast in radio networks with collision detection ⋮ Unnamed Item ⋮ Radio aggregation scheduling ⋮ Deterministic Communication in Radio Networks ⋮ Fast deterministic broadcast and gossiping algorithms for mobile ad hoc networks ⋮ Optimal deterministic broadcasting in known topology radio networks ⋮ Faster communication in known topology radio networks ⋮ Activating anonymous ad hoc radio networks ⋮ Broadcasting in geometric radio networks ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Broadcasting in UDG Radio Networks with Missing and Inaccurate Information ⋮ Efficient Broadcasting in Known Geometric Radio Networks with Non-uniform Ranges ⋮ Lower bounds for the broadcast problem in mobile radio networks ⋮ Deterministic broadcasting in ad hoc radio networks ⋮ Fast Message Dissemination in Random Geometric Ad-Hoc Radio Networks ⋮ Sensor Network Gossiping or How to Break the Broadcast Lower Bound ⋮ The Parameterized Complexity of the Unique Coverage Problem ⋮ Secure and highly-available aggregation queries in large-scale sensor networks via set sampling ⋮ TIME AND ENERGY OPTIMAL LIST RANKING ALGORITHMS ON THE k-CHANNEL BROADCAST COMMUNICATION MODEL WITH NO COLLISION DETECTION ⋮ Modeling radio networks ⋮ The abstract MAC layer ⋮ Coordination Problems in Ad Hoc Radio Networks ⋮ Information Spreading in Dynamic Networks: An Analytical Approach ⋮ 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 ⋮ Efficient Distributed Communication in Ad-Hoc Radio Networks ⋮ Energy-efficient broadcasting in ad hoc wireless networks ⋮ Efficient communication in unknown networks ⋮ Randomized mutual exclusion on a multiple access channel ⋮ Fast radio broadcasting with advice ⋮ Amorphous computing: a research agenda for the near future ⋮ Contention resolution on a fading 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 ⋮ Near-optimal radio use for wireless network synchronization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses ⋮ Token traversal in ad hoc wireless networks via implicit carrier sensing ⋮ Leader election in SINR model with arbitrary power control ⋮ The cost of global broadcast in dynamic radio networks ⋮ On simple back-off in unreliable radio networks ⋮ Global synchronization and consensus using beeps in a fault-prone multiple access channel ⋮ Efficient \(k\)-shot broadcasting in radio networks ⋮ Broadcasting in undirected ad hoc radio networks ⋮ On the universal computing power of amorphous computing systems ⋮ On randomized broadcasting in star graphs ⋮ Design and performance evaluation of communication algorithms in multihop wireless networks with multiple channels ⋮ Nonuniform SINR+Voronoi diagrams are effectively uniform ⋮ Bounded-contention coding for the additive network model ⋮ Broadcasting in dynamic radio networks ⋮ On the effect of the deployment setting on broadcasting in Euclidean radio networks ⋮ Approximate Neighbor Counting in Radio Networks ⋮ Many-to-many communication in radio networks ⋮ Leveraging Channel Diversity to Gain Efficiency and Robustness for Wireless Broadcast ⋮ Conflict-free coloring of unit disks ⋮ Energy efficient randomised communication in unknown AdHoc networks ⋮ Information dissemination in wireless ad-hoc networks under the weighted-TIM framework ⋮ Deterministic recurrent communication in restricted sensor networks ⋮ Time-Efficient Broadcast in Radio Networks ⋮ On Efficient Gossiping in Radio Networks ⋮ Power consumption in packet radio networks ⋮ Leader election in multi-hop radio networks ⋮ Energy-optimal broadcast and exploration in a tree using mobile agents ⋮ 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. ⋮ Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection ⋮ Efficient and competitive broadcast in multi-channel radio networks ⋮ Faster broadcasting in unknown radio networks ⋮ Convergecast and broadcast by power-aware mobile agents
Cites Work
- Unnamed Item
- Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection
- On Broadcasting in Radio Networks--Problem Analysis and Protocol Design
- Born again group testing: Multiaccess communications
- A perspective on multiaccess channels
- Log-Logarithmic Selection Resolution Protocols in a Multiple Access Channel
- A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels
This page was built for publication: On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
