Grossman, Ofer ;
Haeupler, Bernhard ;
Mohanty, Sidhanth
Algorithms for Noisy Broadcast with Erasures
Abstract
The noisy broadcast model was first studied by [Gallager, 1988] where an ncharacter input is distributed among n processors, so that each processor receives one input bit. Computation proceeds in rounds, where in each round each processor broadcasts a single character, and each reception is corrupted independently at random with some probability p. [Gallager, 1988] gave an algorithm for all processors to learn the input in O(log log n) rounds with high probability. Later, a matching lower bound of Omega(log log n) was given by [Goyal et al., 2008].
We study a relaxed version of this model where each reception is erased and replaced with a `?' independently with probability p, so the processors have knowledge of whether a bit has been corrupted. In this relaxed model, we break past the lower bound of [Goyal et al., 2008] and obtain an O(log^* n)round algorithm for all processors to learn the input with high probability. We also show an O(1)round algorithm for the same problem when the alphabet size is Omega(poly(n)).
BibTeX  Entry
@InProceedings{grossman_et_al:LIPIcs:2018:9157,
author = {Ofer Grossman and Bernhard Haeupler and Sidhanth Mohanty},
title = {{Algorithms for Noisy Broadcast with Erasures}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {153:1153:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9157},
URN = {urn:nbn:de:0030drops91576},
doi = {10.4230/LIPIcs.ICALP.2018.153},
annote = {Keywords: noisy broadcast, error correction, erasures, distributed computing with noise}
}
2018
Keywords: 

noisy broadcast, error correction, erasures, distributed computing with noise 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

2018 