On modeling fault tolerance of gossip-based reliable multicast protocols

Xiaopeng Fan, Jiannong Cao, Weigang Wu, Michel Raynal

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)


Gossiping has been widely used for disseminating data in large scale networks. Existing works have mainly focused on the design of gossip-based protocols but few have been reported on developing models for analyzing the fault tolerance property of these protocols. In this paper, we propose a general gossiping algorithm and develop a mathematical model based on generalized random graphs for evaluating the reliability of gossiping, i.e., to what extent gossip-based protocols can tolerate node failures, yet guarantee the specified message delivery. We analytically derive the maximum ratio of failed nodes that can be tolerated without reducing the required degree of reliability. We also investigate the impact of the parameters, namely the fanout distribution and the nonfailed member ratio, on the protocol reliability. Simulations have been carried out to validate the effectiveness of our analytic model in terms of the reliability of gossiping and the success of gossiping. The results obtained can be used to guide the design of fault tolerant gossip-based protocols.
Original languageEnglish
Title of host publicationProceedings - 37th International Conference on Parallel Processing, ICPP 2008
Number of pages8
Publication statusPublished - 17 Nov 2008
Event37th International Conference on Parallel Processing, ICPP 2008 - Portland, OR, United States
Duration: 9 Sep 200812 Sep 2008


Conference37th International Conference on Parallel Processing, ICPP 2008
Country/TerritoryUnited States
CityPortland, OR

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Hardware and Architecture

Cite this