Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/16793
Title: Techniques for improving predictability and message efficiency of gossip protocols
Authors: SATISH KUMAR VERMA
Keywords: Gossip, Epidemic Protocol, Data Dissemination, Hierarchy, Predictability, Asynchronous, Rateless Codes
Issue Date: 28-Jul-2009
Source: SATISH KUMAR VERMA (2009-07-28). Techniques for improving predictability and message efficiency of gossip protocols. ScholarBank@NUS Repository.
Abstract: In this dissertation, we present techniques for improving the predictability and message efficiency of Gossip Protocols. Gossip refers to a simple randomized communication scheme, which can be used to disseminate information to a large set of receivers through a simple message exchange step, i.e., in each step, nodes exchange messages with other nodes which are randomly picked from the respective nodes' membership view. Over a sequence of such steps, the messages spread throughout the system with high probability. Gossip protocols offer improved scalability, reliability, fault-tolerance, stable throughput, and robustness to system dynamics, compared to deterministic techniques. In this work, we address two fundamental shortcomings of gossip, namely, high and random latency of data delivery, and high transmission overhead. The first issue we address is the high and random latency of data delivery that gossip protocols incur while delivering information to a large set of receivers. We introduce a new analytical model called the Asynchronous Gossip Model which leads to faster and predictable data dissemination. Using this new approach, we analyze the behavior of gossip dissemination as a function of time instead of the conventional approach that uses fixed period rounds. We show how gossip performance can be made predictable over time through analysis and simulation. We extend the work on Asynchronous Gossip to design Hierarchical Gossip Protocol which further increases the savings in number of gossip transmissions, reduces the latency of data delivery and more importantly, improves the predictability of Asychronous Gossip Protocol. We evaluate Hierarchical Gossip on a realistic wide area network, the Planetlab. To solve the problem of message overhead, we present Rateless Gossip. Rateless Gossip leverages gossip with Rateless Codes to reduce the message overhead substantially. Compared to tree-based deterministic protocol which requires O(N) transmissions to disseminate a message to a group of N nodes, push-based gossip needs O(N log N) transmissions. Rateless Gossip reduces the gossip overhead by a fraction of 70% or so. An optimized version of Rateless Gossip, i.e., Optimized Rateless Gossip, bounds the message overhead to O(cN) where c is a design parameter.
URI: http://scholarbank.nus.edu.sg/handle/10635/16793
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
VermaSK.pdf1.5 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

309
checked on Dec 11, 2017

Download(s)

385
checked on Dec 11, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.