We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability $\epsilon$. 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 $\Omega(Tn \frac{\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 $\Theta(\log\log n /\log n)$. Our bounds prove that, despite several previous coding schemes with rate $\Omega(1)$ for certain topologies, no coding scheme with constant rate $\Omega(1)$ exists for arbitrary $n$-party noisy networks.