Abstract
dc:description.abstractThis 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 × 1Rights
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