CensorHillel, Keren ;
Haeupler, Bernhard ;
Hershkowitz, D. Ellis ;
Zuzic, Goran
Erasure Correction for Noisy Radio Networks
Abstract
The radio network model is a wellstudied model of wireless, multihop 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 nonadaptive 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 nonadaptive, 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.
BibTeX  Entry
@InProceedings{censorhillel_et_al:LIPIcs:2019:11317,
author = {Keren CensorHillel and Bernhard Haeupler and D. Ellis Hershkowitz and Goran Zuzic},
title = {{Erasure Correction for Noisy Radio Networks}},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
pages = {10:110:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771269},
ISSN = {18688969},
year = {2019},
volume = {146},
editor = {Jukka Suomela},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11317},
URN = {urn:nbn:de:0030drops113170},
doi = {10.4230/LIPIcs.DISC.2019.10},
annote = {Keywords: radio networks, erasure correction, noisy radio networks, protocol simulation, distributed computing models}
}
2019
Keywords: 

radio networks, erasure correction, noisy radio networks, protocol simulation, distributed computing models 
Seminar: 

33rd International Symposium on Distributed Computing (DISC 2019)

Issue date: 

2019 
Date of publication: 

2019 