Randomized broadcast in radio networks with collision detection

DOI10.1007/S00446-014-0230-7MaRDI QIDQ901873zbMATH OpenOpenAlexFDO

Authors Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian

Publication date 6 January 2016

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.0780, http://hdl.handle.net/1721.1/103593

zbMATH Keywords

broadcastcollision detectionradio networksrandom linear network codingwireless networks

Mathematics Subject Classification ID

Distributed systems (68M14) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15) Randomized algorithms (68W20)

Abstract: We present a randomized distributed algorithm that in radio networks with collision detection broadcasts a single message in $O(D+lo{g}^{6}n)$ rounds, with high probability. This time complexity is most interesting because of its optimal additive dependence on the network diameter $D$. It improves over the currently best known $O(DlogfracnD,+,lo{g}^{2}n)$ algorithms, due to Czumaj and Rytter [FOCS 2003], and Kowalski and Pelc [PODC 2003]. These algorithms where designed for the model without collision detection and are optimal in that model. However, as explicitly stated by Peleg in his 2007 survey on broadcast in radio networks, it had remained an open question whether the bound can be improved with collision detection. We also study distributed algorithms for broadcasting $k$ messages from a single source to all nodes. This problem is a natural and important generalization of the single-message broadcast problem, but is in fact considerably more challenging and less understood. We show the following results: If the network topology is known to all nodes, then a $k$-message broadcast can be performed in $O(D+klogn+lo{g}^{2}n)$ rounds, with high probability. If the topology is not known, but collision detection is available, then a $k$-message broadcast can be performed in $O(D+klogn+lo{g}^{6}n)$ rounds, with high probability. The first bound is optimal and the second is optimal modulo the additive $O(lo{g}^{6}n)$ term.

Recommendations

• Randomized broadcast in radio networks with collision detection
• Broadcasting in undirected ad hoc radio networks
• Broadcasting in undirected ad hoc radio networks
• Broadcasting algorithms in radio networks with unknown topology
• Time-efficient randomized multiple-message broadcast in radio networks

Cites work

• A lower bound for radio broadcast
• An Ω(D log(N/D)) lower bound for broadcast in radio networks
• Analyzing network coding gossip made easy
• Broadcast throughput in radio networks: routing vs. network coding
• Broadcasting algorithms in radio networks with unknown topology
• Broadcasting in undirected ad hoc radio networks
• Efficient distributed communication in ad-hoc radio networks
• Faster communication in known topology radio networks
• Multiple Communication in Multihop Radio Networks
• Near optimal leader election in multi-hop radio networks
• On Broadcasting in Radio Networks--Problem Analysis and Protocol Design
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Optimal deterministic broadcasting in known topology radio networks
• Optimal Gossiping with Unit Size Messages in Known Topology Radio Networks
• Time-efficient randomized multiple-message broadcast in radio networks
• What is the use of collision detection (in wireless networks)?

Cited in

(14)

• Exactly optimal deterministic radio broadcasting with collision detection
• Efficient and competitive broadcast in multi-channel radio networks
• A collision model for randomized routing in fat-tree networks
• Time-efficient randomized multiple-message broadcast in radio networks
• What is the use of collision detection (in wireless networks)?
• scientific article; zbMATH DE number 1857647 (Why is no real title available?)
• scientific article; zbMATH DE number 2089983 (Why is no real title available?)
• Randomized broadcast in radio networks with collision detection
• Efficient threshold detection in a distributed environment (extended abstract)
• Reliable broadcast in radio networks
• SOFSEM 2006: Theory and Practice of Computer Science
• Information exchange with collision detection on multiple channels
• Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization
• Broadcasting competitively against adaptive adversary in multi-channel radio networks

This page was built for publication: Randomized broadcast in radio networks with collision detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q901873)