Techniques for improving predictability and message efficiency of gossip protocols

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.