Skip to Main content Skip to Navigation
Conference papers

FoG: fighting the Achilles' heel of gossip protocols with fountain codes

Abstract : Gossip protocols are well known to provide reliable and robust dissemination protocols in highly dynamic systems. Yet, they suffer from high redundancy in the last phase of the dissemination. In this paper, we combine fountain codes (rateless erasure-correcting codes) together with gossip protocols for a robust and fast content dissemination in large-scale dynamic systems. The use of fountain enables to eliminate the unnecessary redundancy of gossip protocols. We propose the design of FoG, which fully exploits the first exponential growth phase (where the data is disseminated exponentially fast) of gossip protocols while avoiding the need for the shrinking phase by using fountain codes. FoG voluntarily increases the number of disseminations but limits those disseminations to the exponential growth phase. In addition, FoG creates a split-graph overlay that splits the peers between encoders and forwarders. Forwarder peers become encoders as soon as they have received the whole content. In order to benefit even further and quicker from encoders, FoG biases the dissemination towards the most advanced peers to make them complete earlier. We assess FoG through simulation. We show that FoG outperforms by 50% a simple push protocol with respect to overhead and improves by 30% the termination time.
Complete list of metadata
Contributor : Nicolas Le Scouarnec <>
Submitted on : Thursday, November 5, 2009 - 2:52:12 PM
Last modification on : Tuesday, June 15, 2021 - 4:16:40 PM


  • HAL Id : inria-00429998, version 1


Mary-Luc Champel, Anne-Marie Kermarrec, Nicolas Le Scouarnec. FoG: fighting the Achilles' heel of gossip protocols with fountain codes. 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2009), Nov 2009, Lyon, France. ⟨inria-00429998⟩



Record views