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(\log^3 n)$ time-steps, only a $\log n$ factor away from the $\Omega(\log^2 n)$ lower bound.
翻译:在无线电网络研究中,广播(在整个网络中传播消息)和领导者选举(使网络就指定“领导者”的节点达成一致)是最基本的两个全局问题,并已经有长期的研究。这项工作有两种分歧方向:一些研究关注利用物理空间中的无线电网络的几何属性,而其他研究则考虑一般图。这些方法的算法结果通常使用非常不同的技术,并使用不可比较的参数化来产生界限。在这项工作中,我们将一般图和基于几何的广播网络的研究合并,通过将Czumaj和Davies(JACM'21)的广播和领导者选举算法适用于独立数的参数化来实现。这种参数化保留了一般图的运行时间,与最佳已知的相匹配,但也将广泛的基于几何的图类的运行时间提高到接近最优。作为该算法的一部分,我们还提供了第一个能够在一般图无线电网络中计算最大独立集的算法。该算法在$O(\log^3 n)$的时间步骤内运行,仅相当于$\Omega(\log^2 n)$的下界,相差不到一倍的因子。