Coding for Distributed Computation

We show that any distributed protocol which runs on a noiseless network in time T, can be simulated on an identical noisy network with a slow-down factor proportional to log(d+1), where d is the maximum degree in the network, and with exponentially small probability of error. On every channel of our network we implement communications using tree codes.