We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability . We analyze the minimal overhead that must be added by the coding scheme in order to succeed in performing the computation despite the noise.

Our main result is a lower bound on the communication of any noise-resilient protocol over a star network with n -parties. Specifically, we show a task that can be solved by communicating Tn bits over the noise-free network, but for which any protocol with success probability of 1 − o (1) must communicate at least ( Tn log n log log n ) bits when the channels are noisy. By a 1994 result of Rajagopalan and Schulman, the slowdown we prove is the highest one can obtain on any topology, up to a log log n factor.

We complete our lower bound with a matching coding scheme that achieves the same overhead; thus, the capacity of star networks is ( log log n log n ) . Our bounds prove that, despite several previous coding schemes with rate (1) for certain topologies, no coding scheme with constant rate (1) exists for arbitrary n -party noisy networks.