We consider the task of multiparty computation performed over networks in the presence of random noise. Given an n-party protocol that takes R rounds assuming noiseless communication, the goal is to find a coding sche...
详细信息
We consider the task of multiparty computation performed over networks in the presence of random noise. Given an n-party protocol that takes R 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 lim infn, R.8 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 time m, then there exists an efficient coding scheme with rate O(1/ m3 logm). 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 n vertices and degrees nO(1).
We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interactive coding scheme which simulates an...
详细信息
We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interactive coding scheme which simulates any asynchronous distributed protocol while tolerating an optimal corruption of a Theta(1/n) fraction of all messages and incurring a moderate blowup of O(nlog2n) in the communication complexity. Our result is the first fully distributed interactive coding scheme in which the topology of the communication network is not known in advance. Prior work required either a coordinating node to be connected to all other nodes in the network or assumed a synchronous network in which all nodes already know the complete topology of the network.
A basic question in any computational model is how to reliably compute a given function when the inputs or intermediate computations are subject to noise at a constant rate. Ideally, one would like to use at most a co...
详细信息
ISBN:
(纸本)9781450312455
A basic question in any computational model is how to reliably compute a given function when the inputs or intermediate computations are subject to noise at a constant rate. Ideally, one would like to use at most a constant factor more resources compared to the noise-free case. This question has been studied for decision trees, circuits, automata, data structures, broadcast networks, communication protocols, and other models. Buhrman et al. (2003) posed the noisy computation problem for real polynomials. We give a complete solution to this problem. For any polynomial p: {0;1}(n) -> [-1;1];we construct a polynomial probust: R-n -> R of degree O(deg p C log 1/epsilon) that epsilon-approximates p and is robust to noise in the inputs: vertical bar p(x) - probust (x + delta)vertical bar < epsilon for all x is an element of{0, 1}(n) and all delta is an element of 2 [-1/3, 1/3](n): This result is optimal with respect to all parameters. We construct p(robust) explicitly for each p. Previously, it was open to give such a construction even for p = x(1) circle plus x(2) ... circle plus x(n) (Buhrman et al., 2003). The proof contributes a technique of independent interest, which allows one to force partial cancellation of error terms in a polynomial.
Beeping networks consist of exceedingly simple computational devices whose communication is based on beeps and silence. In this work, we introduce noisy beeping networks, where the observed communication is noisy with...
详细信息
Beeping networks consist of exceedingly simple computational devices whose communication is based on beeps and silence. In this work, we introduce noisy beeping networks, where the observed communication is noisy with some fixed probability of error. We show how to transform any algorithm over a noiseless beeping network into a noise-resilient version while incurring a multiplicative overhead of essentially O (log n) in its round complexity, with high probability. Our coding is optimal for some (short) tasks, such as the node-coloring of cliques. Interestingly, in the case of coloring, our technique achieves the same complexity as the standard beeping model while being noise resilient. We further show how to simulate a large family of algorithms designed for distributed networks in the CONGEST(B) model over a noisy beeping network, with a multiplicative overhead of O (B center dot A center dot min(n, A2)) in the round complexity, where A is the maximum degree of the network. (c) 2022 Elsevier Inc. All rights reserved.
暂无评论