# Reliable Communication over Highly Connected Noisy Networks

## Author(s): Alon, Noga; Braverman, Mark; Efremenko, Klim; Gelles, Ran; Haeupler, Bernhard

DownloadTo refer to this page use:

`http://arks.princeton.edu/ark:/88435/pr13m8w`

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 inf(n,R ->infinity) 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(Omega(1)). |

Publication Date: | 2016 |

Citation: | Alon, Noga, Braverman, Mark, Efremenko, Klim, Gelles, Ran, Haeupler, Bernhard. (2016). Reliable Communication over Highly Connected Noisy Networks. PROCEEDINGS OF THE 2016 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC’16), 165 - 173. doi:10.1145/2933057.2933085 |

DOI: | doi:10.1145/2933057.2933085 |

Pages: | 165 - 173 |

Type of Material: | Journal Article |

Journal/Proceeding Title: | PROCEEDINGS OF THE 2016 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC’16) |

Version: | Author's manuscript |

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