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.ITCS.2018.50
URN: urn:nbn:de:0030-drops-83184
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8318/
Go to the corresponding LIPIcs Volume Portal

Censor-Hillel, Keren ; Gelles, Ran ; Haeupler, Bernhard

Making Asynchronous Distributed Computations Robust to Channel Noise

pdf-format:
LIPIcs-ITCS-2018-50.pdf (0.6 MB)

Abstract

We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interactive coding scheme which simulates any asynchronous distributed protocol while tolerating a maximal corruption level of \Theta(1/n)-fraction of all messages. Our noise tolerance is optimal and is obtained with only a moderate overhead in the number of messages.
Our result is the first fully distributed interactive coding scheme in which the topology of the communication network is not known in advance. Prior work required either a coordinating node to be connected to all other nodes in the network or assumed a synchronous network in which all nodes already know the complete topology of the network.
Overcoming this more realistic setting of an unknown topology leads to intriguing distributed problems, in which nodes try to learn sufficient information about the network topology in order to perform efficient coding and routing operations for coping with the noise. What makes these problems hard is that these topology exploration computations themselves must already be robust to noise.

BibTeX - Entry

@InProceedings{censorhillel_et_al:LIPIcs:2018:8318,
  author =	{Keren Censor-Hillel and Ran Gelles and Bernhard Haeupler},
  title =	{{Making Asynchronous Distributed Computations Robust to Channel Noise}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{50:1--50:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Anna R. Karlin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8318},
  URN =		{urn:nbn:de:0030-drops-83184},
  doi =		{10.4230/LIPIcs.ITCS.2018.50},
  annote =	{Keywords: Distributed Computation, Coding for Interactive Communication, Noise- Resilient Computation, Coding Theory}
}

Keywords: Distributed Computation, Coding for Interactive Communication, Noise- Resilient Computation, Coding Theory
Collection: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Issue Date: 2018
Date of publication: 12.01.2018

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