Randomized Rumor Spreading---Talking to More or Less Random People

Randomized Rumor Spreading is a simple mechanism to distribute
a piece of information (rumor) in a network. It builds on the paradigm
that vertices call random neighbors to send or retrieve information. In
spite of its simplicity and the lack of central coordination, such
mechanisms spread a rumor initially present at a single vertex to all
others in logarithmic time if the graph is sufficiently nice (e.g., a
complete graph, a hypercube, a random graph G(n,p), p not too small, and
many others).

In the talk, I will discuss two recent results on randomized rumor
spreading. (i) How to improve the rumor spreading protocol adding simple
dependencies to the random decisions of the vertices. (ii) How fast is
rumor spreading in social networks, in particular, preferential
attachment graphs?