Back to search

Graduate Studies

Analysis of Asynchronous and Synchronous Rumor Spreading Protocols

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MSc)
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher.institution
Graduate Studies
Year dc:date.issued
2016

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Nazari, Yasamin
Advisors dc:contributor.advisor
  • Woelfel, Philipp
  • Giakkoupis, George

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.
Language dc:language.iso
eng

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
University of Calgary
Base URL
ucalgary.scholaris.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Nazari, Yasamin. Analysis of Asynchronous and Synchronous Rumor Spreading Protocols. Graduate Studies, 2016. http://hdl.handle.net/11023/3136