  The best known solutions for $k$-message broadcast in dynamic networks of
size $n$ require $\Omega(nk)$ rounds. In this paper, we see if these bounds can
be improved by smoothed analysis. We study perhaps the most natural randomized
algorithm for disseminating tokens in this setting: at every time step, choose
a token to broadcast randomly from the set of tokens you know. We show that
with even a small amount of smoothing (one random edge added per round), this
natural strategy solves $k$-message broadcast in $\tilde{O}(n+k^3)$ rounds,
with high probability, beating the best known bounds for $k=o(\sqrt{n})$ and
matching the $\Omega(n+k)$ lower bound for static networks for $k=O(n^{1/3})$
(ignoring logarithmic factors). In fact, the main result we show is even
stronger and more general: given $\ell$-smoothing (i.e., $\ell$ random edges
added per round), this simple strategy terminates in
$O(kn^{2/3}\log^{1/3}(n)\ell^{-1/3})$ rounds. We then prove this analysis close
to tight with an almost-matching lower bound. To better understand the impact
of smoothing on information spreading, we next turn our attention to static
networks, proving a tight bound of $\tilde{O}(k\sqrt{n})$ rounds to solve
$k$-message broadcast, which is better than what our strategy can achieve in
the dynamic setting. This confirms that although smoothed analysis reduces the
difficulties induced by changing graph structures, it does not eliminate them
altogether. Finally, we apply our tools to prove an optimal result for
$k$-message broadcast in so-called well-mixed networks in the absence of
smoothing. By comparing this result to an existing lower bound for well-mixed
networks, we establish a formal separation between oblivious and strongly
adaptive adversaries with respect to well-mixed token spreading, partially
resolving an open question on the impact of adversary strength on the
$k$-message broadcast problem.
