Radio Network Lower Bounds Made Easy

DOI10.1007/978-3-662-45174-8_18MaRDI QIDQ5498700zbMATH OpenOpenAlexFDO

Authors Calvin Newport

Publication date 10 February 2015

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

Full work available at URL https://arxiv.org/abs/1405.7300

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15) Applications of game theory (91A80)

Abstract: Theoreticians have studied distributed algorithms in the radio network model for close to three decades. A significant fraction of this work focuses on lower bounds for basic communication problems such as wake-up (symmetry breaking among an unknown set of nodes) and broadcast (message dissemination through an unknown network topology). In this paper, we introduce a new technique for proving this type of bound, based on reduction from a probabilistic hitting game, that simplifies and strengthens much of this existing work. In more detail, in this single paper we prove new expected time and high probability lower bounds for wake-up and global broadcast in single and multichannel versions of the radio network model both with and without collision detection. In doing so, we are able to reproduce results that previously spanned a half-dozen papers published over a period of twenty-five years. In addition to simplifying these existing results, our technique, in many places, also improves the state of the art: of the eight bounds we prove, four strictly strengthen the best known previous result (in terms of time complexity and/or generality of the algorithm class for which it holds), and three provide the first known non-trivial bound for the case in question. The fact that the same technique can easily generate this diverse collection of lower bounds indicates a surprising unity underlying communication tasks in the radio network model---revealing that deep down, below the specifics of the problem definition and model assumptions, communication in this setting reduces to finding efficient strategies for a simple game.

Recommendations

• Lower Bounds for Clear Transmissions in Radio Networks
• Improved lower bound for deterministic broadcasting in radio networks
• A lower bound for radio broadcast
• STACS 2004
• Lower bounds for the broadcast problem in mobile radio networks
• Lower bounds for structuring unreliable radio networks
• Faster broadcasting in unknown radio networks
• Some complexity results about packet radio networks (Corresp.)
• Faster communication in known topology radio networks
• Faster communication in known topology radio networks

Cited in

(15)

• A lower bound for radio broadcast
• Contention resolution on a fading channel
• The cost of global broadcast in dynamic radio networks
• On simple back-off in unreliable radio networks
• Modeling Radio Networks
• Lower Bounds for Clear Transmissions in Radio Networks
• Bounding the maximum size of a packet radio network
• Contention resolution with constant throughput and log-logstar channel accesses
• Approximate Neighbor Counting in Radio Networks
• Leader election in SINR model with arbitrary power control
• Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election
• On the computational power of radio channels
• Optimal Protocols for 2-Party Contention Resolution
• Modeling radio networks
• On the complexity of neighbourhood learning in radio networks

This page was built for publication: Radio Network Lower Bounds Made Easy

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