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

Davies, Peter

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(log3 n) time-steps, only a log n factor away from the Ω(log2 n) lower bound.

Citation

Davies, P. (2023, June). Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization. Presented at PODC 2023: ACM Symposium on Principles of Distributed Computing, Orlando, Florida

• Presentation Conference Type: Conference Paper (published)
• Conference Name: PODC 2023: ACM Symposium on Principles of Distributed Computing
• Start Date: Jun 19, 2023
• End Date: Jun 23, 2023
• Acceptance Date: Mar 26, 2023
• Online Publication Date: Jun 16, 2023
• Publication Date: 2023-06
• Deposit Date: Apr 3, 2023
• Publicly Available Date: Aug 15, 2023
• Pages: 290-299
• DOI: https://doi.org/10.1145/3583668.3594595
• Public URL: https://durham-repository.worktribe.com/output/1134396