Skip to main content

Reliable Communication over Highly Connected Noisy Networks

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

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr13m8w
Full metadata record
DC FieldValueLanguage
dc.contributor.authorAlon, Noga-
dc.contributor.authorBraverman, Mark-
dc.contributor.authorEfremenko, Klim-
dc.contributor.authorGelles, Ran-
dc.contributor.authorHaeupler, Bernhard-
dc.date.accessioned2019-08-29T17:02:02Z-
dc.date.available2019-08-29T17:02:02Z-
dc.date.issued2016en_US
dc.identifier.citationAlon, 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.2933085en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr13m8w-
dc.description.abstractWe 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)).en_US
dc.format.extent165 - 173en_US
dc.language.isoen_USen_US
dc.relation.ispartofPROCEEDINGS OF THE 2016 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC’16)en_US
dc.rightsAuthor's manuscripten_US
dc.titleReliable Communication over Highly Connected Noisy Networksen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1145/2933057.2933085-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
meshconst6.pdf358.74 kBAdobe PDFView/Download


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