Skip to main content

Reliable communication over highly connected noisy networks

Author(s): Alon, N; Braverman, Mark; Efremenko, K; Gelles, R; Haeupler, B

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr14h31
Abstract: 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).
Publication Date: 25-Jul-2016
Electronic Publication Date: 2016
Citation: Alon, N, Braverman, M, Efremenko, K, Gelles, R, Haeupler, B. (2017). Reliable communication over highly connected noisy networks. Distributed Computing, 1 - 11. doi:10.1007/s00446-017-0303-5
DOI: doi:10.1145/2933057.2933085
Pages: 1 - 11
Type of Material: Conference Article
Journal/Proceeding Title: PODC '16 Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.