Welcome to the resource topic for 2017/710
Title:
Distributed Computing with Channel Noise
Authors: Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, Jared Saia
Abstract:A group of n users want to run a distributed protocol \pi over a network where communication occurs via private point-to-point channels. Unfortunately, an adversary, who knows \pi, is able to maliciously flip bits on the channels. Can we efficiently simulate \pi in the presence of such an adversary? We show that this is possible, even when L, the number of bits sent in \pi, and T, the number of bits flipped by the adversary are not known in advance. In particular, we show how to create a robust version of \pi that 1) fails with probability at most \delta, for any \delta > 0; and 2) sends \tilde{O}(L+T) bits, where the \tilde{O} notation hides a \log(nL/\delta) term multiplying L. Additionally, we show how to improve this result when the average message size \alpha is not constant. In particular, we give an algorithm that sends O(L(1 + (1/\alpha) \log(nL/\delta) + T ) bits. This algorithm is adaptive in that it does not require a priori knowledge of \alpha. We note that if \alpha is \Omega (log(nL/\delta)), then this improved algorithm sends only O(L + T) bits, and is therefore within a constant factor of optimal.
ePrint: https://eprint.iacr.org/2017/710
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .