How to Spread a Rumor: Call Your Neighbors or Take a Walk?
Published version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Abstract
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