Recent Advances in Randomized Rumor Spreading
Randomized rumor spreading is a fundamental randomized primitive for broadcasting information in networks, in a simple, efficient, and fault-tolerant manner. It was proposed more than 30 years ago, but it has been intensively studied over the last few years. In the first half of the talk, I will give an overview of selected recent results in the area. A standard assumption in the analysis of randomized rumor spreading has been that nodes take steps in perfectly synchronized rounds. In the second half of the talk, I will present some new results on the impact of relaxing this strict synchrony assumption.