Please use this identifier to cite or link to this item:
Title: Effects of erasures on gossiping algorithms
Authors: Lee, Qiu Xiang.
Keywords: DRNTU::Engineering::Computer science and engineering::Computing methodologies::Simulation and modeling
DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
Issue Date: 2011
Abstract: Second generation networks have emerged in the recent years. These networks are set up for a specific primary purpose other than for communication. Examples of such networks are P2P networks, sensor networks, vehicular networks and social networks. These networks, similar to the internet, also require algorithms to execute the primary objective that needs to be served. Taking for example, sensor networks may need to sense for data, monitor for events and in some cases, as an alerting source to inform the user about a certain event occurring. Intelligent vehicular networks may need to inform other vehicles in the network about its accident. Gossip algorithms have been considered for employment in second generation networks due to its scalability, its simplicity and robustness. In gossiping networks, a node with information wishes to disseminate its information to all the nodes in a rumor-like style. In this report, the dissemination of single piece and multipiece information in a complete graph is studied. Erasures in the link connecting two nodes are considered to occur independently with a probability, indicated by q. The main objective of the analysis is to study the effects that independent erasures have on the ε-dissemination time (time when the spreading of message have completed with a probability of at least 1-ε) of the algorithm. Push based gossiping is used for single piece dissemination and push-pull based gossiping is used for the analysis if multipiece dissemination. The algorithm is modeled using Matlab and simulation is carried out to analyse the effects that erasures have on the ε-dissemination time.
Rights: Nanyang Technological University
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:EEE Student Reports (FYP/IA/PA/PI)

Files in This Item:
File Description SizeFormat 
  Restricted Access
1.57 MBAdobe PDFView/Open

Page view(s) 50

checked on Oct 28, 2020

Download(s) 50

checked on Oct 28, 2020

Google ScholarTM


Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.