The noisy broadcast model was first studied in [Gallager, TranInf'88] where an @math -character input is distributed among @math 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 @math . [Gallager, TranInf'88] gave an algorithm for all processors to learn the input in @math rounds with high probability. Later, a matching lower bound of @math was given in [Goyal, Kindler, Saks; SICOMP'08]. We study a relaxed version of this model where each reception is erased and replaced with a ?' independently with probability @math . In this relaxed model, we break past the lower bound of [Goyal, Kindler, Saks; SICOMP'08] and obtain an @math -round algorithm for all processors to learn the input with high probability. We also show an @math -round algorithm for the same problem when the alphabet size is @math .
A broadcast network of N+1 nodes is considered in which each binary digit transmitted by each node is received by every other node via a binary symmetric channel of given transition probability. The errors on these channels are independent over transmitters, receivers and time. Each node has a binary state, and the problem is to construct a distributed algorithm to find the parity of the set of states with some given reliability. It is shown that this can be done with O(ln(lnN)) bits of communication from each node. Communicating all the node states to one node can be accomplished with only marginally more communication. >