License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.53
URN: urn:nbn:de:0030-drops-181059
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18105/
Go to the corresponding LIPIcs Volume Portal

Efremenko, Klim ; Kol, Gillat ; Paramonov, Dmitry ; Saxena, Raghuvansh R.

Protecting Single-Hop Radio Networks from Message Drops

pdf-format:
LIPIcs-ICALP-2023-53.pdf (0.8 MB)

Abstract

Single-hop radio networks (SHRN) are a well studied abstraction of communication over a wireless channel. In this model, in every round, each of the n participating parties may decide to broadcast a message to all the others, potentially causing collisions. We consider the SHRN model in the presence of stochastic message drops (i.e., erasures), where in every round, the message received by each party is erased (replaced by ⊥) with some small constant probability, independently.
Our main result is a constant rate coding scheme, allowing one to run protocols designed to work over the (noiseless) SHRN model over the SHRN model with erasures. Our scheme converts any protocol Π of length at most exponential in n over the SHRN model to a protocol Π' that is resilient to constant fraction of erasures and has length linear in the length of Π.
We mention that for the special case where the protocol Π is non-adaptive, i.e., the order of communication is fixed in advance, such a scheme was known. Nevertheless, adaptivity is widely used and is known to hugely boost the power of wireless channels, which makes handling the general case of adaptive protocols Π both important and more challenging. Indeed, to the best of our knowledge, our result is the first constant rate scheme that converts adaptive protocols to noise resilient ones in any multi-party model.

BibTeX - Entry

@InProceedings{efremenko_et_al:LIPIcs.ICALP.2023.53,
  author =	{Efremenko, Klim and Kol, Gillat and Paramonov, Dmitry and Saxena, Raghuvansh R.},
  title =	{{Protecting Single-Hop Radio Networks from Message Drops}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{53:1--53:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18105},
  URN =		{urn:nbn:de:0030-drops-181059},
  doi =		{10.4230/LIPIcs.ICALP.2023.53},
  annote =	{Keywords: Radio Networks, Interactive Coding, Error Correcting Codes}
}

Keywords: Radio Networks, Interactive Coding, Error Correcting Codes
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI