CensorHillel, Keren ;
Gelles, Ran ;
Haeupler, Bernhard
Making Asynchronous Distributed Computations Robust to Channel Noise
Abstract
We consider the problem of making distributed computations robust to noise, in particular to worstcase (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 CensorHillel 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:150:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770606},
ISSN = {18688969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8318},
URN = {urn:nbn:de:0030drops83184},
doi = {10.4230/LIPIcs.ITCS.2018.50},
annote = {Keywords: Distributed Computation, Coding for Interactive Communication, Noise Resilient Computation, Coding Theory}
}
2018
Keywords: 

Distributed Computation, Coding for Interactive Communication, Noise Resilient Computation, Coding Theory 
Seminar: 

9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Issue date: 

2018 
Date of publication: 

2018 