2017/02/23 by Keren Censor-Hillel, Censor-Hillel, Keren, Ran Gelles +3 · 2 citations
Computer Science · #Cooperative Communication and Network Coding #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.1702.07403
arxiv created 2017/02/23 · openalex publication_date 2017/02/23 · arxiv updated 2017/02/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interactive coding scheme which simulates any asynchronous distributed protocol while tolerating an optimal corruption of a Θ(1/n) fraction of all messages while incurring a moderate blowup of O(nlog2 n) in the communication complexity. Our result is the first fully distributed interactive coding scheme in which the topology of the communication network is not known in advance. Prior work required either a coordinating node to be connected to all other nodes in the network or assumed a synchronous network in which all nodes already know the complete topology of the network.