Effects of erasures on gossiping algorithms

• Main Author: Lee, Qiu Xiang.
• Other Authors: School of Electrical and Electronic Engineering
• Format: Final Year Project
• Language: English
• Published: 2011
• Subjects: 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
• Online Access: http://hdl.handle.net/10356/45967
• Institution: Nanyang Technological University

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.