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 @math fraction of all messages while incurring a moderate blowup of @math 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.
@cite_36: Distributed computing models typically assume reliable communication between processors. While such assumptions often hold for engineered networks, e.g., due to underlying error correction protocols, their relevance to biological systems, wherein messages are often distorted before reaching their destination, is quite limited. In this study we aim at bridging this gap by rigorously analyzing a model of communication in large anonymous populations composed of simple agents which interact through short and highly unreliable messages. We focus on the rumor-spreading problem and the majority-consensus problem, two fundamental tasks in distributed computing, and initiate their study under communication noise. Our model for communication is extremely weak and follows the push gossip communication paradigm: In each synchronous round each agent that wishes to send information delivers a message to a random anonymous agent. This communication is further restricted to contain only one bit (essentially representing an opinion). Lastly, the system is assumed to be so noisy that the bit in each message sent is flipped independently with probability 1 2-e, for some small Ae >0. Even in this severely restricted, stochastic and noisy setting we give natural protocols that solve the noisy rumor-spreading and the noisy majority-consensus problems efficiently. Our protocols run in O(log n e2) rounds and use O(n log n e2) messages bits in total, where n is the number of agents. These bounds are asymptotically optimal and, in fact, are as fast and message efficient as if each agent would have been simultaneously informed directly by the source. Our efficient, robust, and simple algorithms suggest balancing between silence and transmission, synchronization, and majority-based decisions as important ingredients towards understanding collective communication schemes in anonymous and noisy populations.
@cite_5: We consider the problem of communication between nodes of a network whose links are subject to arbitrary failures: A failed link may not only stop transmitting messages but may corrupt them in any possible way. We characterize networks allowing communication in spite of at most t failures. Also, for every fixed link failure probability p ≤ .29, we construct a class of networks for which the probability of successful communication converges to 1 as the number of nodes grows. It is shown that the number of links in these networks is asymptotically smallest possible to assure reliable communication. Moreover, in these networks, communication can be completed in just two information exchange rounds. Finally, we give a protocol assuring reliable communication in the hypercube if link failure probability is p ≤ .02 and show that no such protocol exists if p ≥ .15.
Pelc @cite_5 shows that if the number of Byzantine-corrupted links is bounded by @math , reliable communication is achievable only over graphs whose connectivity is more than @math . The same work also considers the case where each link is faulty with some probability. In a more recent work, Feinerman, Haeupler and Korman @cite_36 also address complete synchronous networks, and study the specific problems of broadcast and majority consensus under random errors.