Analysis of Asynchronous and Synchronous Rumor Spreading Protocols

Abstract

This thesis focuses on a class of randomized broadcasting algorithms known as rumor spreading algorithms. In these algorithms, initially one node in a network has a rumor, and nodes exchange the rumor with one of their randomly chosen neighbors. In the originally proposed rumor spreading algorithms, nodes take steps in synchronous rounds. More recently, an arguably more realistic asynchronous model was proposed in which nodes take steps independently of each other. In this thesis, we first provide formal definitions for the basic concepts used in the literature. We then formally prove that several known models are equivalent. Next, we present several upper bounds on the running time of the push protocol on general graphs that improve the currently known upper bounds. Finally, we show that in the asynchronous model, the push protocol has twice the running time of the push-pull protocol on regular graphs.