Asynchronous vs. Synchronous Rumor Spreading

Our intended research will be focused on rumor spreading protocols, also known as randomized broadcasting. In the randomized rumor spreading problem, the goal is to broadcast a message that is initiated at one node to all nodes in a given network, by means of nodes choosing uniformly at random a neighbor and exchanging the message with that neighbor. We can assume two models for these algorithms: a synchronous model in which nodes communicate in synchronized steps (in parallel), and an asynchronous model in which each node has an independent clock that it uses for communication. Most of the current literature focused on the synchronous model. We want to compare the performance of protocols known for these two models to see if the results that hold for the synchronous model also hold for the asynchronous model.

Faculty Supervisor:

Philipp Woelfel

Student:

Yasamin Nazari

Partner:

Discipline:

Computer science

Sector:

University:

University of Calgary

Program:

Globalink