We will be receiving Hayk Saribekyan from the University of Cambridge who will give a talk “How to spread a rumour: call your neighbours or take a walk?” on Tuesday, November the 12th.
Abstract: We study the problem of randomized information dissemination in networks. We compare the now standard push-pull protocol, with an agent-based alternative visit-exchange, 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 information they have.
We consider the broadcast times of a single piece of information in an n-node graph, assuming a linear number of agents, that start from the stationary distribution. We observe that there are graphs on which the agent-based protocols as significantly faster than push-pull, and graphs where the converse is true. We attribute the good performance of visit-exchange 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. This is joint work with George Giakkoupis and Frederik Mallmann-Trenn.
