  We consider the problem of reliable epidemic dissemination of a rumor in a
fully connected network of~$n$ processes using push and pull operations. We
revisit the random phone call model and show that it is possible to disseminate
a rumor to all processes with high probability using $\Theta(\ln n)$ rounds of
communication and only $n+o(n)$ messages of size $b$, all of which are
asymptotically optimal and achievable with pull and push-then-pull algorithms.
This contradicts two highly-cited lower bounds of Karp et al. stating that any
algorithm in the random phone call model running in $\mathcal{O}(\ln n)$ rounds
with communication peers chosen uniformly at random requires at least
$\omega(n)$ messages to disseminate a rumor with high probability, and that any
address-oblivious algorithm needs $\Omega(n \ln \ln n)$ messages regardless of
the number of communication rounds. The reason for this contradiction is that
in the original work, processes do not have to share the rumor once the
communication is established. However, it is implicitly assumed that they
always do so in the proofs of their lower bounds, which, it turns out, is not
optimal. Our algorithms are strikingly simple, address-oblivious, and robust
against $\epsilon n$ adversarial failures and stochastic failures occurring
with probability $\delta$ for any $0 \leq \{\epsilon,\delta\} < 1$.
Furthermore, they can handle multiple rumors of size $b \in \omega(\ln n \ln
\ln n)$ with $nb + o(nb)$ bits of communication per rumor.
