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 paper by Feige and Killian @cite_2 studied a harsher noise model than @cite_1 , where an adversary can arbitrarily uncorrupt' arbitrary corrupted bits, causing the noise to lose structure. In this harsher model, they show an @math round protocol to compute the OR of all input bits. Newman @cite_15 studies another noise model where each bit transmitted is independently flipped with an unknown probability that is at most @math and gives algorithms that use @math broadcasts and @math rounds for certain classes of Boolean functions, including OR , AND , and functions with linear size @math formulas.
@cite_15 @cite_1 @cite_2
2144590858 2053269541 2035902142
We consider a fault tolerance broadcast network of n processors each holding one bit of information. The goal is to compute a given Boolean function on the n bits. In each step, a processor may broadcast one bit of information. Each listening processor receives the bit that was broadcasted with error probability bounded by a fixed constant spl epsi . The errors in different steps, as well as for different receiving processors in the same step, are mutually independent. The protocols that are considered in this model are oblivious protocols: At each step, the processors that broadcast are fixed in advanced and independent of the input and the outcome of previous steps. The primal complexity measure in this model is the total number of broadcasts that is performed by the protocol. We present here the first linear complexity protocols for several classes of Boolean functions, including the OR function, functions that have O(l)-minterm (maxterm) size, functions that have linear size AC sub 0 formulae and some other functions. This answer an open question of Yao (1997), considering this fault tolerance model of El-Gamal (1984) and Gallager (1988). 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. > Abstract We consider a broadcast network of n processors in which each bit transmitted by each processor is received by each other processor via a noisy channel. Each processor has a binary input, and the problem is to construct a reliable distributed algorithm to determine whether at least one processor has the input 1. We show that this can be done with O ( log ∗ n) bits of communication from each processor, under an adversarial noise model. In this model, a processor receives a broadcasted bit correctly with some base probability q . The adversary may choose to correct the values of corrupted messages, but may not corrupt the values of correctly received messages.