License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2019.13
URN: urn:nbn:de:0030-drops-117999
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11799/
Go to the corresponding LIPIcs Volume Portal

Gelles, Ran ; Iyer, Siddharth

Interactive Coding Resilient to an Unknown Number of Erasures

pdf-format:
LIPIcs-OPODIS-2019-13.pdf (0.5 MB)

Abstract

We consider distributed computations between two parties carried out over a noisy channel that may erase messages. Following a noise model proposed by Dani et al. (2018), the noise level observed by the parties during the computation in our setting is arbitrary and a priori unknown to the parties.
We develop interactive coding schemes that adapt to the actual level of noise and correctly execute any two-party computation. Namely, in case the channel erases T transmissions, the coding scheme will take N+2T transmissions using an alphabet of size 4 (alternatively, using 2N+4T transmissions over a binary channel) to correctly simulate any binary protocol that takes N transmissions assuming a noiseless channel. We can further reduce the communication to N+T by relaxing the communication model and allowing parties to remain silent rather than forcing them to communicate in every round of the coding scheme.
Our coding schemes are efficient, deterministic, have linear overhead both in their communication and round complexity, and succeed (with probability 1) regardless of the number of erasures T.

BibTeX - Entry

@InProceedings{gelles_et_al:LIPIcs:2020:11799,
  author =	{Ran Gelles and Siddharth Iyer},
  title =	{{Interactive Coding Resilient to an Unknown Number of Erasures}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11799},
  URN =		{urn:nbn:de:0030-drops-117999},
  doi =		{10.4230/LIPIcs.OPODIS.2019.13},
  annote =	{Keywords: Interactive coding, erasure channels, distributed computation with noise, unbounded noise}
}

Keywords: Interactive coding, erasure channels, distributed computation with noise, unbounded noise
Collection: 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
Issue Date: 2020
Date of publication: 11.02.2020

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