Bounds on contention management in radio networks

DOI10.1007/978-3-642-33651-5_16MaRDI QIDQ4909414zbMATH OpenOpenAlexFDO

Authors Mohsen Ghaffari, Bernhard Haeupler, Calvin Newport, Nancy Lynch

Publication date 13 March 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Abstract: The local broadcast problem assumes that processes in a wireless network are provided messages, one by one, that must be delivered to their neighbors. In this paper, we prove tight bounds for this problem in two well-studied wireless network models: the classical model, in which links are reliable and collisions consistent, and the more recent dual graph model, which introduces unreliable edges. Our results prove that the Decay strategy, commonly used for local broadcast in the classical setting, is optimal. They also establish a separation between the two models, proving that the dual graph setting is strictly harder than the classical setting, with respect to this primitive.

Recommendations

• Broadcasting in unreliable radio networks
• On simple back-off in unreliable radio networks
• The cost of radio network broadcast for different models of unreliable links
• A lower bound for radio broadcast
• Bounded-contention coding for the additive network model

Cited in

(9)

• On simple back-off in unreliable radio networks
• CONTENTION RESOLUTION IN MULTIPLE-ACCESS CHANNELS: k-SELECTION IN RADIO NETWORKS
• Contention Resolution in Multiple-Access Channels: k-Selection in Radio Networks
• Bounding the maximum size of a packet radio network
• Bounded-contention coding for wireless networks in the high SNR regime
• On simple back-off in unreliable radio networks
• Structuring unreliable radio networks
• Congestion, dilation, and energy in radio networks
• Bounded-contention coding for the additive network model

This page was built for publication: Bounds on contention management in radio networks

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