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.
Type de document :
Communication dans un congrès
11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2009), Nov 2009, Lyon, France. 2009
Liste complète des métadonnées

https://hal.inria.fr/inria-00429998
Contributeur : Nicolas Le Scouarnec <>
Soumis le : jeudi 5 novembre 2009 - 14:52:12
Dernière modification le : mercredi 16 mai 2018 - 11:23:13

Identifiants

  • HAL Id : inria-00429998, version 1

Citation

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. 2009. 〈inria-00429998〉

Partager

Métriques

Consultations de la notice

369