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

DOI10.1145/3583668.3594595arXiv2303.16832OpenAlexW4380881513WikidataQ130964633 ScholiaQ130964633MaRDI QIDQ6202265FDOQ6202265

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)

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.

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)

Cites Work

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

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)