  We study lower bounds on information dissemination in adversarial dynamic
networks. Initially, k pieces of information (henceforth called tokens) are
distributed among n nodes. The tokens need to be broadcast to all nodes through
a synchronous network in which the topology can change arbitrarily from round
to round provided that some connectivity requirements are satisfied.
  If the network is guaranteed to be connected in every round and each node can
broadcast a single token per round to its neighbors, there is a simple token
dissemination algorithm that manages to deliver all k tokens to all the nodes
in O(nk) rounds. Interestingly, in a recent paper, Dutta et al. proved an
almost matching Omega(n + nk/log n) lower bound for deterministic
token-forwarding algorithms that are not allowed to combine, split, or change
tokens in any way. In the present paper, we extend this bound in different
ways.
  If nodes are allowed to forward b < k tokens instead of only one token in
every round, a straight-forward extension of the O(nk) algorithm disseminates
all k tokens in time O(nk/b). We show that for any randomized token-forwarding
algorithm, Omega(n + nk/(b^2 log n log log n)) rounds are necessary. If nodes
can only send a single token per round, but we are guaranteed that the network
graph is c-vertex connected in every round, we show a lower bound of
Omega(nk/(c log^{3/2} n)), which almost matches the currently best O(nk/c)
upper bound. Further, if the network is T-interval connected, a notion that
captures connection stability over time, we prove that Omega(n + nk/(T^2 log
n)) rounds are needed. The best known upper bound in this case manages to solve
the problem in O(n + nk/T) rounds. Finally, we show that even if each node only
needs to obtain a delta-fraction of all the tokens for some delta in [0,1],
Omega(nk delta^3 log n) are still required.
