2026-07-22T16:55:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24488 2025-12-16T13:59:50Z ddc:004 open_access

Beeping Deterministic CONGEST Algorithms in Graphs Garncarek, Pawel Kowalski, Dariusz R. Kutten, Shay Mosteiro, Miguel A. Beeping Networks CONGEST Networks deterministic simulations graph algorithms 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 Õ(Δ²). 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pawel Garncarek and Dariusz R. Kowalski and Shay Kutten and Miguel A. Mosteiro 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.20 urn:nbn:de:0030-drops-244880 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.20 eng https://creativecommons.org/licenses/by/4.0/legalcode