Reliable Communication over Highly Connected Noisy Networks
Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler · Distributed Computing · 2016
We consider the task of multiparty computation performed over networks in the presence of random noise. Given an n -party protocol that takes R rounds assuming noiseless communication, the goal is to find a coding scheme that takes \(R'\) rounds and computes the same function with high probability even when the communication is noisy, while maintaining a constant asymptotic rate , i.e., while keeping \(\liminf _{n,R\rightarrow \infty } R/R'\) positive. Rajagopalan and Schulman (STOC ’94) were the first to consider this question, and provided a coding scheme with rate \(O(1/\log (d+1))\) , where d is the maximal degree in the network. While that scheme provides a constant rate coding for many practical situations, in the worst case, e.g., when the network is a complete graph, the rate is \(O(1/\log n)\) , which tends to 0 as n tends to infinity. We revisit this question and provide an efficient coding scheme with a constant rate for the interesting case of fully connected networks. We furthermore extend the result and show that if a ( d -regular) network has mixing time m , then there exists an efficient coding scheme with rate \(O(1/m^3\log m)\) . This implies a constant rate coding scheme for any n -party protocol over a d -regular network with a constant mixing time, and in particular for random graphs with n vertices and degrees \(n^{\varOmega (1)}\) .