Paper 2017/710

Distributed Computing with Channel Noise

Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, and 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 $$. Additionally, we show how to improve this result when the average message size $$ is not constant. In particular, we give an algorithm that sends $$ bits. This algorithm is adaptive in that it does not require a priori knowledge of $$. We note that if $$ is $$, then this improved algorithm sends only $$ bits, and is therefore within a constant factor of optimal.