Reliable communication over highly connected noisy networks

作     者：Alon, Noga Braverman, Mark Efremenko, Klim Gelles, Ran Haeupler, Bernhard 

作者机构：Tel Aviv Univ Sackler Sch Math IL-69978 Tel Aviv Israel Tel Aviv Univ Blavatnik Sch Comp Sci IL-69978 Tel Aviv Israel Princeton Univ Dept Comp Sci Princeton NJ 08540 USA Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Bar Ilan Univ Fac Engn IL-52900 Ramat Gan Israel Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA 

出 版 物：《DISTRIBUTED COMPUTING》 (分布式计算)

年 卷 期：2019年第32卷第6期

页      面：505-515页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Israel Science Foundation, ISF Israeli I-Core United States-Israel Binational Science Foundation, BSF European Commission, EC Seventh Framework Programme, FP7 Simons Foundation National Science Foundation, NSF, (1527110, CCF-1149888, DMS-1128155, CCF-1525342, 1933331, NSF-BSF) Seventh Framework Programme, FP7, (CCF-1618280, CCF-1527110, 257575) Center for Selective C-H Functionalization, National Science Foundation, (CCF-1527110) 

主　　题：Coding theory Random noise Interactive coding Computation with noise 

摘      要：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.8 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 nO(1).