Files in this item



application/pdfScheduling of Multi-Stream Gossip Systems.pdf (184kB)
(no description provided)PDF


Title:Scheduling of Multi-Stream Gossip Systems
Author(s):Thompson, Nathanael A.; Ucan, Ercan; Gupta, Indranil
gossip systems
distributed systems
Abstract:Many distributed applications are beginning to employ gossip-based message dissemination, where the burden of content distribution is shared democratically among the recipient nodes, e.g., for RSS distribution. However, such systems have many communication channels, i.e., multiple gossip streams may be present within the same application, e.g., an RSS content distribution system involves several publishers sending out streams to overlapping groups of subscribers ( i.e., "nodes"). Yet, most existing gossiping approaches tend to have nodes treat each gossip stream independently of one another. This leads to each node being burdened with a message overhead that is the sum from all gossip streams. In this paper, we show that if all nodes instead use a scheduling strategy on the multiple gossip streams that they receive and forward, this leads to a significant reduction in overhead, but without affecting the original reliability, scalability, or latency. Simply put, our approach piggybacks messages from streams atop one another. However, in doing so, we take into account the different frequencies of gossiping for streams, and affinities of streams to one another. We formulate these constraints in a new model that we call the "semblance graph". After formally stating our gossip scheduling problem, we show that finding an optimal solution to it is an NP-complete problem. We then present two greedy heuristics for the problem, one being Prim-like and the other being Kruskal-like (though the MST problem is different from ours). Our experimental results are in two categories . (1) a semblance graph-based evaluation that shows the heuristics come within 3.5% of the optimal solution, and (2) a distributed system simulation that shows the message savings are up to 85% compared to the default gossiping approach without scheduling.
Issue Date:2006-05
Genre:Technical Report
Other Identifier(s):UIUCDCS-R-2006-2726
Rights Information:You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS:2009-04-21

This item appears in the following Collection(s)

Item Statistics