Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication

摘要: 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 biological systems, wherein messages are distorted before reaching destination, is quite limited. In this study we take a first step towards reducing gap by rigorously analyzing model of in large anonymous populations composed simple agents which interact through short and highly unreliable messages. We focus on the broadcast problem majority-consensus problem. Both fundamental information dissemination problems distributed computing, goal converge some prescribed desired opinion. initiate these presence noise. Our extremely weak follows push gossip paradigm: each round agent that wishes send delivers message random agent. This further restricted contain only one bit (essentially representing an opinion). Lastly, system assumed be so noisy sent flipped independently with probability $$1/2-\epsilon $$ , small $$\epsilon >0$$ . Even severely restricted, stochastic setting give natural protocols solve efficiently. run $$O(\log n/\epsilon ^2)$$ rounds use $$O(n \log n / \epsilon messages/bits total, where number agents. These bounds asymptotically optimal and, fact, as fast efficient if would have been simultaneously informed directly knows efficient, robust, algorithms suggest balancing silence transmission, synchronization, majority-based decisions important ingredients understanding collective schemes populations.