Beeping Deterministic CONGEST Algorithms in Graphs

Beeping Network (BN) is a popular graph-based model of wireless computation, which applies the OR operation to one-bit messages sent simultaneously by neighbors. It admits fast (polylogarithmic in the number of nodes n) randomized solutions to many graph problems, but all known deterministic algorithms for non-trivial graph problems are at least polynomial in the maximum node degree ∆. We improve known results for deterministic algorithms by showing that this polynomial can be as low as O^e(∆²). More precisely, we show how to simulate a single round of any CONGEST algorithm in any network in O(∆² polylog n) beeping rounds, each accommodating at most one beep per node, even if the nodes intend to send different messages to different neighbors. This upper bound reduces polynomially the time for a deterministic simulation of CONGEST in a Beeping Network, comparing to the best known algorithms, and nearly matches the time obtained recently using randomization (up to a poly-logarithmic factor) as well as the lower bound. Specifically, any algorithm designed for the CONGEST networks can be run in BNs with O(∆² polylog n) multiplicative overhead, e.g., we can now deterministically compute an MIS in any BN in O(∆² polylog n) beeping rounds, improving the previous best Θ(∆³)-round solution. For h-hop simulations, we prove a lower bound Ω(∆^h+1), and we design a nearly matching algorithm that is able to “pipeline” the node-to-node information in a faster way than beeping layer-by-layer.