  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 take a first step towards
reducing 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 broadcast problem and the majority-consensus problem. Both
are fundamental information dissemination problems in distributed computing, in
which the goal of agents is to converge to some prescribed desired opinion. We
initiate the study of these problems in the presence of communication noise.
Our model for communication is extremely weak and follows the push gossip
communication paradigm: In each 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-\epsilon$, for some
small $\epsilon >0$.
  Even in this severely restricted, stochastic and noisy setting we give
natural protocols that solve the noisy broadcast and the noisy
majority-consensus problems efficiently. Our protocols run in $O(\log n /
\epsilon^2)$ rounds and use $O(n \log n / \epsilon^2)$ 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 an agent that knows the prescribed desired
opinion.
