Computer Science

News and events

5 July 2017

Distributed Computing with Channel Noise

Presented By Prof Jared Saia, University of New Mexico
  • N.1.12, Haslegrave Building

About this event


A group of n users want to run a distributed protocol π over a network where communication occurs via private point-to-point channels. Unfortunately, an adversary, who knows π, is able to maliciously flip bits on the channels. Can we efficiently simulate π in the presence of such an adversary?

We show that this is possible, even when L, the number of bits sent in π, 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 π that 1) fails with probability at most ε, for any ε>0; and 2) sends Õ(L + T) bits, where the Õ notation hides logarithmic terms.

Additionally, we show how to improve this result when the average message size α is not constant. In particular, we give an algorithm that sends O(L+T) bits when α is logarithmic in L,n, T and 1/ε. This algorithm does not require a priori knowledge of α.