Lecturer: Prof. Pierluigi Crescenzi

Period: 8-16 Luglio, 2013


Rumor spreading is a well-known gossip-based distributed algorithm for disseminating information in large networks. According to the synchronous push version of this algorithm, an arbitrary source node is initially informed, and, at each time step (a.k.a., round), an informed node u chooses one of its neighbors v uniformly at random, and this node becomes informed at the next time step. In the symmetric pull version of the algorithm, at each time step, a not informed node u randomly chooses one of its neighbors v; if v is informed, then u becomes informed at the next time step.

Finally, the push-and-pull version is a combination of the two previous versions, in which, at each time step, each informed node executes a "push operation", and each not informed node executes a "pull operation". Rumor spreading was first introduced in the context of replicated databases, as a solution to the problem of distributing updates and driving replicas towards consistency. Successively, it has been proposed in several other application areas, such as failure detection in distributed systems, peer-sampling, adaptive machine discovery, and distributed averaging in sensor networks. Apart from its applications, rumor spreading has also been deeply analyzed from a theoretical and mathematical point of view. In particular, the completion time of rumor spreading, that is, the number of steps required in order to have all nodes informed, has been investigated in the case of several different network topologies, such as complete graphs, hypercubes, random graphs, and preferential attachment graphs. Besides obtaining bounds on the completion time of  rumor spreading, most of these works also derive deep connections between the completion time itself and some classic measures of graph spectral theory, such as, for example, the conductance of a graph. The techniques and the arguments adopted in these studies strongly rely on the fact that the underlying graph is "static" and does not change over time. It is then natural to ask ourselves what is the speed of rumor spreading in the case of "dynamic" networks, where nodes and edges can appear and disappear over time (several emerging networking technologies such as ad hoc wireless, sensor, mobile networks, and peer-to-peer networks are indeed inherently dynamic). In this dynamic environment, even in the case of the simplest communication protocol that implements the broadcast operation, that is, the flooding protocol (according to which a source node is initially informed, and, whenever  an uninformed node has an informed neighbor, it becomes informed itself at the next time step), it has been shown that evolving graphs can exhibit communication properties which are much stronger than static networks. In this course, we will first review several results concerning the completion time of rumor spreading in the case of static networks. We will then present some results concerning the completion time of the flooding protocol, which have been obtained in the case of some interesting graph evolution models. Finally, we will present very recent results concerning the completion time of the push version of rumor spreading in the case of dynamic graphs.

Place: Sala Seminari Ovest


Lunedi' 8 Luglio: 9-12
Lunedi' 8 Luglio: 15-17
Martedi' 9 Luglio: 9-12
Martedi' 9 Luglio: 15-17

Lunedi' 15 Luglio: 9-12
Lunedi' 15 Luglio: 15-17
Martedi' 16 Luglio: 9-12
Martedi' 16 Luglio: 15-17