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 .
In @cite_11 , the authors show efficient protocols to handle errors in the UCAST model, in which instead of broadcasting bits, a processor can send a different message to each other processor. They also show efficient protocols to handle errors when the communication network has certain expansion properties. For general graphs of low degree, a protocol for handling errors was found in @cite_0 , which was later shown to be optimal in @cite_9 .
@cite_0 @cite_9 @cite_11
2077242989 2483713254
In this dissertation, we prove a coding theorem for distributed network protocols. We show that any distributed protocol which runs on a noiseless network in time T, can be simulated on an identical noisy network with a slow-down factor proportional to log(d + 1), where d is the maximum degree in the network, and with exponentially small probability of error. Our theorem is a network analog of the classical coding theorem of Shannon (1948), which addresses the issue of the transmission of data over a noisy link. Although Shannon's original theorem is non-constructive--it proves the existence of codes that transfer data at asymptotically optimal rates--the subsequent development of coding theory makes this result constructive. Shannon's theory, however, does not address issues that arise when noise occurs in the communications of a wide area computational network with a number of links available for simultaneous use. This question of what happens when computation is interleaved with noisy communications was proposed and first addressed by Schulman in the special case of a pair of computers connected by a bidirectional communication link. In this case, Schulman obtains an analog of Shannon's theorem. Like those of Shannon and Schulman, the results we exhibit are non constructive. However, in our case, it is possible to obtain constructive simulations by compromising the reliability with which they run. For a particular problem, the 'telephone' game, we exhibit a constructive solution for which this compromise is unnecessary. Work reported in this dissertation stems from that done jointly with Leonard Schulman. We consider the task of multiparty computation performed over networks in the presence of random noise. Given an n-party protocol that takes @math rounds assuming noiseless communication, the goal is to find a coding scheme that takes R' rounds and computes the same function with high probability even when the communication is noisy, while maintaining a constant asymptotic rate, i.e., while keeping n,R→∞ R R' positive. Rajagopalan and Schulman (STOC '94) were the first to consider this question, and provided a coding scheme with rate O(1 log (d+1)), where d is the maximal degree in the network. While that scheme provides a constant rate coding for many practical situations, in the worst case, e.g., when the network is a complete graph, the rate is O(1 log n), which tends to 0 as n tends to infinity. We revisit this question and provide an efficient coding scheme with a constant rate for the interesting case of fully connected networks. We furthermore extend the result and show that if a (d-regular) network has mixing timem, then there exists an efficient coding scheme with rate O(1 m3log m). This implies a constant rate coding scheme for any n-party protocol over a d-regular network with a constant mixing time, and in particular for random graphs with @math vertices and degrees nΩ(1).