Efficient epidemic-style protocols for reliable and scalable multicast

Indranil Gupta, Anne Marie Kermarrec, Ayalvadi J. Ganesh

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Epidemic-style (gossip-based) techniques have recently emerged as a scalable class of protocols for peer-to-peer reliable multicast dissemination in large process groups. These protocols provide probabilistic guarantees on reliability and scalability. However, popular implementations of epidemic-style dissemination are reputed to suffer from two major drawbacks: (a) (Network Overhead) when deployed on a WAN-wide or VPN-wide scale they generate a large number of packets that transit across the boundaries of multiple network domains (e.g., LANs, subnets, ASs), causing an overload on core network elements such as bridges, routers, and associated links; (b) (Lack of Adaptivity) they impose the same load on process group members and the network even under reduced failure rates (viz., packet losses, process failures). In this paper, we report on the (first) comprehensive set of solutions to these problems. The solution is comprised of two protocols: (1) a Hierarchical Gossiping protocol, and (2) an Adaptive multicast Dissemination Framework that allows use of any gossiping primitive within it. These protocols work within a virtual peer-to-peer hierarchy called the Leaf Box Hierarchy. Processes can be allocated in a topologically aware manner to the leaf boxes of this structure, so that (1) and (2) produce low traffic across domain boundaries in the network. In the interests of space, this paper focuses on a detailed discussion and evaluation (through simulations) of only the Hierarchical Gossiping protocol. We present an overview of the Adaptive Dissemination protocol and its properties.

Original languageEnglish (US)
Title of host publicationProceedings of the IEEE Symposium on Reliable Distributed Systems
Number of pages10
StatePublished - 2002
Externally publishedYes
EventThe 21st IEEE Symposium on Reliable Distributed Systems (SRDS-2002) - Suita, Japan
Duration: Oct 13 2002Oct 16 2002

Publication series

NameProceedings of the IEEE Symposium on Reliable Distributed Systems
ISSN (Print)1060-9857


OtherThe 21st IEEE Symposium on Reliable Distributed Systems (SRDS-2002)

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Efficient epidemic-style protocols for reliable and scalable multicast'. Together they form a unique fingerprint.

Cite this