  We study the problem of randomized information dissemination in networks. We
compare the now standard PUSH-PULL protocol, with agent-based alternatives
where information is disseminated by a collection of agents performing
independent random walks. In the VISIT-EXCHANGE protocol, both nodes and agents
store information, and each time an agent visits a node, the two exchange all
the information they have. In the MEET-EXCHANGE protocol, only the agents store
information, and exchange their information with each agent they meet.
  We consider the broadcast time of a single piece of information in an
$n$-node graph for the above three protocols, assuming a linear number of
agents that start from the stationary distribution. We observe that there are
graphs on which the agent-based protocols are significantly faster than
PUSH-PULL, and graphs where the converse is true. We attribute the good
performance of agent-based algorithms to their inherently fair bandwidth
utilization, and conclude that, in certain settings, agent-based information
dissemination, separately or in combination with PUSH-PULL, can significantly
improve the broadcast time.
  The graphs considered above are highly non-regular. Our main technical result
is that on any regular graph of at least logarithmic degree, PUSH-PULL and
VISIT-EXCHANGE have the same asymptotic broadcast time. The proof uses a novel
coupling argument which relates the random choices of vertices in PUSH-PULL
with the random walks in VISIT-EXCHANGE. Further, we show that the broadcast
time of MEET-EXCHANGE is asymptotically at least as large as the other two's on
all regular graphs, and strictly larger on some regular graphs.
  As far as we know, this is the first systematic and thorough comparison of
the running times of these very natural information dissemination protocols.

Distributed, Parallel, and Cluster Computing;Discrete Mathematics