Scheduling of Multi-Stream Gossip Systems

Thompson, Nathanael A.; Ucan, Ercan; Gupta, Indranil

Permalink

https://hdl.handle.net/2142/11204 Copy

Description

Title

Scheduling of Multi-Stream Gossip Systems

Author(s)

• Thompson, Nathanael A.
• Ucan, Ercan
• Gupta, Indranil

Issue Date

2006-05

Keyword(s)

• scheduling
• 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."

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11204

Copyright and License 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).

Owning Collections