2026-08-03T00:50:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11317 2024-03-06T10:47:56Z ddc:004 open_access

Erasure Correction for Noisy Radio Networks Censor-Hillel, Keren Haeupler, Bernhard Hershkowitz, D. Ellis Zuzic, Goran radio networks erasure correction noisy radio networks protocol simulation distributed computing models The radio network model is a well-studied model of wireless, multi-hop networks. However, radio networks make the strong assumption that messages are delivered deterministically. The recently introduced noisy radio network model relaxes this assumption by dropping messages independently at random. In this work we quantify the relative computational power of noisy radio networks and classic radio networks. In particular, given a non-adaptive protocol for a fixed radio network we show how to reliably simulate this protocol if noise is introduced with a multiplicative cost of poly(log Delta, log log n) rounds where n is the number nodes in the network and Delta is the max degree. Moreover, we demonstrate that, even if the simulated protocol is not non-adaptive, it can be simulated with a multiplicative O(Delta log ^2 Delta) cost in the number of rounds. Lastly, we argue that simulations with a multiplicative overhead of o(log Delta) are unlikely to exist by proving that an Omega(log Delta) multiplicative round overhead is necessary under certain natural assumptions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Keren Censor-Hillel and Bernhard Haeupler and D. Ellis Hershkowitz and Goran Zuzic 2019 Is Part Of LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2019.10 urn:nbn:de:0030-drops-113170 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.10 eng https://creativecommons.org/licenses/by/3.0/legalcode