We consider computations over networks with multiple broadcast channels that intersect at a single party. Each broadcast link suffers from random bit-flip noise that affects the receivers independently. We design inte...
详细信息
We consider computations over networks with multiple broadcast channels that intersect at a single party. Each broadcast link suffers from random bit-flip noise that affects the receivers independently. We design interactive coding schemes that successfully perform any computation over these noisy networks and strive to reduce their communication overhead with respect to the original (noiseless) computation. A simple variant of a coding scheme by Rajagopalan and Schulman (STOC 1994) shows that any (noiseless) protocol of R rounds can be reliably simulated in O(Rlog n) rounds over a network with n = n(1)n(2) + 1 parties in which a single party is connected to n(2) noisy broadcast channels, each of which connects n(1) distinct parties. We design new coding schemes with improved overheads. Our approach divides the network into four regimes according to the relationship between n(1) and n(2). We employ a two-layer coding where the inner code protects each broadcast channel and is tailored to the specific conditions of the regime in consideration. The outer layer protects the computation in the network and is generally based on the scheme of Rajagopalan and Schulman, adapted to the case of broadcast channels. The overhead we obtain ranges from O(log log n(2)) to O(log n(2) log log n(1)/log n(1)) and beats the trivial O(log n) overhead in all four regimes.
The field of interactive coding studies how an interactive protocol can be made resilient to channel errors. Even though this field has received abundant attention since Schulman's seminal paper (FOCS 92), constru...
详细信息
ISBN:
(纸本)9781728196213
The field of interactive coding studies how an interactive protocol can be made resilient to channel errors. Even though this field has received abundant attention since Schulman's seminal paper (FOCS 92), constructing interactive coding schemes that are both deterministic and efficient, and at the same time resilient to adversarial errors (with constant information and error rates), remains an elusive open problem. An appealing approach towards resolving this problem is to construct an efficiently encodable and decodable combinatorial object called a tree code (Schulman, STOC 93). After a lot of effort in this direction, the current state of the art has deterministic constructions of tree codes that are efficiently encodable but require an alphabet of size logarithmic (instead of constant) in the depth of the tree code (Cohen, Haeupler, and Schulman, STOC 18). We emphasize that we still lack (even heuristic) candidate constructions that are efficiently decodable. In this work, we show that tree codes that are efficiently encodable, but not efficiently decodable, also imply deterministic and efficient interactive coding schemes that are resilient to adversarial errors. Our result immediately implies a deterministic and efficient interactive coding scheme with a logarithmic alphabet (i.e., 1/log log rate). We show this result using a novel implementation of hashing through deterministic tree codes that is powerful enough to yield interactive coding schemes.
interactive coding, pioneered by Schulman (FOCS '92, STOC '93), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small consta...
详细信息
interactive coding, pioneered by Schulman (FOCS '92, STOC '93), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman et al. proposed a far-reaching generalization of this model, whereby the adversary can additionally manipulate the channel by removing and inserting symbols. For any epsilon > 0, they showed how to faithfully simulate any protocol in this model with corruption rate up to 1/18 - epsilon, using a constant-size alphabet and a constant-factor overhead in communication. We give an optimal simulation of any protocol in this generalized model of substitutions, insertions, and deletions, tolerating a corruption rate up to 1/4 - epsilon, while keeping the alphabet to a constant size and the communication overhead to a constant factor. This resolves a question due to Gelles (2015). Our corruption tolerance matches an impossibility result for corruption rate 1/4 which holds even for substitutions alone (Braverman and Rao, STOC '11).
In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that can tol...
详细信息
ISBN:
(纸本)9781450362177
In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that can tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate). In this work we consider synchronous communication networks over an arbitrary topology, in the powerful adversarial insertion-deletion noise model. Namely, the noisy channel may adversarially alter the content of any transmitted symbol, as well as completely remove a transmitted symbol or inject a new symbol into the channel. We provide efficient, constant rate schemes that successfully conduct any computation with high probability as long as the adversary corrupts at most epsilon/m fraction of the total communication, where m is the number of links in the network and epsilon is a small constant. This scheme assumes an oblivious adversary which is independent of the parties' inputs and randomness. We can remove this assumption and resist a worst-case adversary at the price of being resilient to epsilon/m log m errors. While previous work considered the insertion-deletion noise model in the two-party setting, to the best of our knowledge, our scheme is the first multiparty scheme that is resilient to insertions and deletions. Furthermore, our scheme is the first computationally efficient scheme in the multiparty setting that is resilient to adversarial noise.
A set of n players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the ...
详细信息
ISBN:
(纸本)9781450355599
A set of n players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit received by each player is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed? This problem was first suggested by El Gamal in 1984. In 1988, Gallager gave an elegant noise-resistant protocol requiring only O(n log logn) rounds. The problem got resolved in 2005 by a seminal paper of Goyal, Kindler, and Saks, proving that Gallager's protocol is essentially optimal. We revisit the above noisy broadcast problem and showthat O(n) rounds suffice. This is possible due to a relaxation of the model assumed by the previous works. We no longer demand that exactly one player broadcasts in every round, but rather allow any number of players to broadcast. However, if it is not the case that exactly one player chooses to broadcast, each of the other players gets an adversely chosen bit. We generalized the above result and initiate the study of interactive coding over the noisy broadcast channel. We show that any interactive protocol that works over the noiseless broadcast channel can be simulated over our restrictive noisy broadcast model with constant blowup of the communication.
interactive coding, pioneered by Schulman (FOCS '92, STOC '93), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small consta...
详细信息
ISBN:
(纸本)9781538634646
interactive coding, pioneered by Schulman (FOCS '92, STOC '93), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky (2015) proposed a far-reaching generalization of this model, whereby the adversary can additionally manipulate the channel by removing and inserting symbols. They showed how to faithfully simulate any protocol in this model with corruption rate up to 1/18, using a constant-size alphabet and a constant-factor overhead in communication. We give an optimal simulation of any protocol in this generalized model of substitutions, insertions, and deletions, tolerating a corruption rate up to 1/4 while keeping the alphabet to a constant size and the communication overhead to a constant factor. Our corruption tolerance matches an impossibility result for corruption rate 1/4 which holds even for substitutions alone (Braverman and Rao, STOC '11).
The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOGS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one tha...
详细信息
ISBN:
(纸本)9781450333337
The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOGS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of adversarial error, while blowing up the communication by only a constant factor. In this work we extend the work of Schulman to the multiparty setting. We show how to convert any (non-adaptive) n-party protocol into one that is resilient to Theta(1/n)-fraction of adversarial error, while blowing up the communication by only a constant factor. One might hope to get resilience to constant-fraction of errors, by restricting the adversary's error distribution, and allowing him to make at most a constant-fraction of errors per party. We present a black-box lower bound, showing that we cannot be resilient to such adversarial errors, even if we increase the communication by an arbitrary polynomial factor, assuming the error-resilient protocol has a fixed (non-adaptive) speaking order.
Consider two parties who wish to communicate in order to execute some interactive protocol pi. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channe...
详细信息
Consider two parties who wish to communicate in order to execute some interactive protocol pi. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant fraction of the bits arbitrarily, thus interrupting the execution of (which was designed for an error-free channel). If pi only contains a single long message, then a good error correcting code would overcome the noise with only a constant overhead in communication. However, this solution is not applicable to interactive protocols consisting of many short messages. Schulman [1992, 1993] introduced the notion of interactive coding: A simulator that, given any protocol pi, is able to simulate it (i.e., produce its intended transcript) even in the presence of constant rate adversarial channel errors, and with only constant (multiplicative) communication overhead. However, the running time of Schulman's simulator, and of all simulators that followed, has been exponential (or subexponential) in the communication complexity of pi (which we denote by N). In this work, we present three efficient simulators, all of which are randomized and have a certain failure probability (over the choice of coins). The first runs in time poly(N), has failure probability roughly 2(-N), and is resilient to 1/32-fraction of adversarial error. The second runs in time 0(N log N), has failure probability roughly 2-N, and is resilient to some constant fraction of adversarial error. The third runs in time 0(N), has failure probability 1/poly(N), and is resilient to some constant fraction of adversarial error. (Computational complexity is measured in the RAM model.) The first two simulators can be made deterministic if they are a priori given a random string (which may be known to the adversary ahead of time). In particular, the simulators can be made to be nonuniform and deterministic (with equivalent performance). Categories and Subject Descriptors: E.4 [
Kol and Raz [STOC 2013] showed how to simulate any alternating two-party communication protocol designed to work over the noiseless channel, by a protocol that works over a stochastic channel that corrupts each sent s...
详细信息
ISBN:
(纸本)9781450399135
Kol and Raz [STOC 2013] showed how to simulate any alternating two-party communication protocol designed to work over the noiseless channel, by a protocol that works over a stochastic channel that corrupts each sent symbol with probability epsilon > 0 independently, with only a 1 + O(root H(epsilon)) blowup to the communication. In particular, this implies that the maximum rate of such interactive codes approaches 1 as epsilon goes to 0, as is also the case for the maximum rate of classical error correcting codes. Over the past decade, followup works have strengthened and generalized this result to other noisy channels, stressing on how fast the rate approaches 1 as epsilon goes to 0, but retaining the assumption that the noiseless protocol is alternating. In this paper we consider the general case, where the noiseless protocols can have arbitrary orders of speaking. In contrast to Kol-Raz and to the followup results in this model, we show that the maximum rate of interactive codes that encode general protocols is upper bounded by a universal constant strictly smaller than 1. To put it differently, we show that there is an inherent blowup in communication when protocols with arbitrary orders of speaking are faced with any constant fraction of errors epsilon > 0. We mention that our result assumes a large alphabet set and resolves the (non-binary variant) of a conjecture by Haeupler [FOCS 2014].
In their seminal PODC 1991 paper, Ostrovsky and Yung introduced the study of distributed computation in the presence of mobile adversaries which can dynamically appear throughout the network, analogous to a spread of ...
详细信息
ISBN:
(纸本)9798400701214
In their seminal PODC 1991 paper, Ostrovsky and Yung introduced the study of distributed computation in the presence of mobile adversaries which can dynamically appear throughout the network, analogous to a spread of a virus. Over the years, this setting has been studied mostly under the assumption that the communication graph is fully-connected. Resilient CONGEST algorithms for general graphs, on the other hand, are currently known only for the classical static setting, i.e., where the set of corrupted edges (or nodes) is fixed throughout the entire computation. We fill this missing gap by providing round-efficient simulations that translate given CONGEST algorithms into equivalent algorithms that are resilient against f-mobile edge adversaries, i.e., where the adversary controls a (possibly distinct) subset of f edges F-i in each round i. Our main results are: center dot Perfect-Security with Mobile Eavesdroppers. A translation of any r-round f-static-secure algorithm into an equivalent Theta(f)-mobile-secure algorithm with Theta(y) rounds. We also show that the f-static-secure algorithms of [Hitron, Parter and Yogev, DISC 2022 & ITCS 2023] can be modified into f-mobile-secure algorithms with the same number of rounds. center dot Resilience with Mobile Byzantine Adversaries. An f-mobile-byzantine simulation which is based on a decomposition of the graph into low-diameter edge-disjoint spanning trees. This provides us with near-optimal CONGEST compilers for expander graphs. It also leads to near-optimal compilers in the congested-clique model against Theta(n)-mobile adversaries. For general (2f + 1) edge-connected graphs with f-mobile adversary, we almost match the bounds known for the f-static setting, when provided a trusted pre-processing phase. Our results are based on a collection of tools borrowed from the area of interactive coding [Gelles, Found. Trends Theor. Comput. Sci. 2017], linear sketches and low-congestion graph decomposition. The introduced toolkit
暂无评论