Information dissemination via random walks

Abstract

Information dissemination is a fundamental task in distributed computing: How to deliver a piece of information from a node of a network to some or all other nodes? In the face of large and still growing modern networks, it is imperative that dissemination algorithms are decentralised and can operate under unreliable conditions. In the past decades, randomised rumour spreading algorithms have addressed these challenges. In these algorithms, a message is initially placed at a source node of a network, and, at regular intervals, each node contacts a randomly selected neighbour. A message may be transmitted in one or both directions during each of these communications, depending on the exact protocol. The main measure of performance for these algorithms is their broadcast time, which is the time until a message originating from a source node is disseminated to all nodes of the network. Apart from being extremely simple and robust to failures, randomised rumour spreading achieves theoretically optimal broadcast time in many common network topologies.

In this thesis, we propose an agent-based information dissemination algorithm, called Visit-Exchange. In our protocol, a number of agents perform independent random walks in the network. An agent becomes informed when it visits a node that has a message, and later informs all future nodes it visits. Visit-Exchange shares many of the properties of randomised rumour spreading, namely, it is very simple and uses the same amount of communication in a unit of time. Moreover, the protocol can be used as a simple model of non-recoverable epidemic processes.

We investigate the broadcast time of Visit-Exchange on a variety of network topologies, and compare it to traditional rumour spreading. On dense regular networks we show that the two types of protocols are equivalent, which means that in this setting the vast literature on randomised rumour spreading applies in our model as well. Since many networks of interest, including real-world ones, are very sparse, we also study agent-based broadcast for sparse networks. Our results include almost optimal or optimal bounds for sparse regular graphs, expanders, random regular graphs, balanced trees and grids. We establish that depending on the network topology, Visit-Exchange may be either slower or faster than traditional rumour spreading. In particular, in graphs consisting of hubs that are not well connected, broadcast using agents can be significantly faster. Our conclusion is that a combined broadcasting protocol that simultaneously uses both traditional rumour spreading and agent-based dissemination can be fast on a larger range of topologies than each of its components separately.