2026-07-22T18:25:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9157 2024-03-06T10:43:30Z ddc:004 open_access

Algorithms for Noisy Broadcast with Erasures Grossman, Ofer Haeupler, Bernhard Mohanty, Sidhanth noisy broadcast error correction erasures distributed computing with noise The noisy broadcast model was first studied by [Gallager, 1988] where an n-character 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)). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ofer Grossman and Bernhard Haeupler and Sidhanth Mohanty 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.153 urn:nbn:de:0030-drops-91576 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.153 eng https://creativecommons.org/licenses/by/3.0/legalcode