Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization

DOI10.1145/3583668.3594595MaRDI QIDQ6202265zbMATH OpenOpenAlexWikidataFDO

Authors P. Davies

Publication date 26 March 2024

Published in Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

broadcastingleader electionmaximal independent setradio networks

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: In the study of radio networks, the tasks of broadcasting (propagating a message throughout the network) and leader election (having the network agree on a node to designate `leader') are two of the most fundamental global problems, and have a long history of work devoted to them. This work has two divergent strands: some works focus on exploiting the geometric properties of wireless networks based in physical space, while others consider general graphs. Algorithmic results in each of these avenues have often used quite different techniques, and produced bounds using incomparable parametrizations. In this work, we unite the study of general-graph and geometric-based radio networks, by adapting the broadcast and leader election algorithm of Czumaj and Davies (JACM '21) to achieve a running-time parametrized by the independence number of the network (i.e., the size of the maximum independent set). This parametrization preserves the running time on general graphs, matching the best known, but also improves running times to near-optimality across a wide range of geometric-based graph classes. As part of this algorithm, we also provide the first algorithm for computing a maximal independent set in general-graph radio networks. This algorithm runs in $O(lo{g}^{3}n)$ time-steps, only a $logn$ factor away from the $Omega(lo{g}^{2}n)$ lower bound.

Cites work

• A Faster Distributed Radio Broadcast Primitive
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A lower bound for radio broadcast
• An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks
• An Improved Distributed Algorithm for Maximal Independent Set
• Broadcast in the Ad Hoc SINR Model
• Broadcasting algorithms in radio networks with unknown topology
• Broadcasting in UDG radio networks with unknown topology
• Broadcasting in geometric radio networks
• Deterministic communication in radio networks
• Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks
• Faster Deterministic Broadcasting in Ad Hoc Radio Networks
• Leader election in multi-hop radio networks
• Lower Bounds for Clear Transmissions in Radio Networks
• Maximal independent sets in multichannel radio networks
• Near optimal leader election in multi-hop radio networks
• On selection problem in radio networks
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Randomized broadcast in radio networks with collision detection
• Tight bounds for MIS in multichannel radio networks
• What is the use of collision detection (in wireless networks)?
• \textsc{Maximal Independent Sets} in radio networks

This page was built for publication: Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization

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