TY - GEN

T1 - Reliable communication over highly connected noisy networks

AU - Alon, Noga

AU - Braverman, Mark

AU - Efremenko, Klim

AU - Gelles, Ran

AU - Haeupler, Bernhard

N1 - Funding Information:
Research supported in part by a USA-Israeli BSF grant, by an ISF grant, by the Israeli I-Core program and by the Oswald Veblen Fund. Research supported in part by an NSF CAREER award (CCF-1149888), a Turing Centenary Fellowship, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry. Research supported in part by: European Communitys Seventh Framework Programme (FP7/2007-2013) under grant agreement number 257575.

PY - 2016/7/25

Y1 - 2016/7/25

N2 - 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 lim infn,R→∞ 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/m3 logm). 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ω(1).

AB - 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 lim infn,R→∞ 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/m3 logm). 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ω(1).

UR - http://www.scopus.com/inward/record.url?scp=84984710635&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84984710635&partnerID=8YFLogxK

U2 - 10.1145/2933057.2933085

DO - 10.1145/2933057.2933085

M3 - Conference contribution

AN - SCOPUS:84984710635

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 165

EP - 173

BT - PODC 2016 - Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

T2 - 35th ACM Symposium on Principles of Distributed Computing, PODC 2016

Y2 - 25 July 2016 through 28 July 2016

ER -