On Gossip and populations

Marin Bertier 1 Yann Busnel 2 Anne-Marie Kermarrec 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
2 PARIS - Programming distributed parallel systems for large scale numerical simulation
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, ENS Cachan - École normale supérieure - Cachan, Inria Rennes – Bretagne Atlantique
Abstract : Gossip protocols are simple, robust and scalable and have been consistently applied to many (mostly wired) distributed systems. Nevertheless, most validation in this area has been so far empirical and there is a clear lack of a theoretical counterpart to characterize what can and cannot be computed with gossip protocols. Population protocols, on the other hand, benefit from a sound theoretical framework but little empirical evaluation. In this paper, we establish a correlation between population and Gossip-based protocols. We propose a classification of gossip-based protocols, based on the nature of the underlying peer sampling service. First, we show that the class of gossip protocols, where each node relies on an arbitrary sample, is equivalent to population protocols. Second, we show that gossip-based protocols, relying on a more powerful peer sampling providing peers using a clearly identified set of other peers, are equivalent to community protocols, a modern variant of population protocols. Leveraging the resemblances between these areas enables to provide a theoretical framework for distributed systems where global behaviors emerge from a set of local interactions, both in wired and wireless settings. Likewise, the practical validations of gossip-protocols provide empirical evidence of quick convergence times of such algorithms and demonstrate their practical relevance. While existing results in each area can be immediately applied, this also leaves the space to transfer any new results, practical or theoretical, from one domain to the other.
Type de document :
Communication dans un congrès
16th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2009), May 2009, Piran, Slovenia. 2009
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

Contributeur : Marin Bertier <>
Soumis le : mardi 1 décembre 2009 - 15:27:40
Dernière modification le : jeudi 15 novembre 2018 - 11:57:35
Document(s) archivé(s) le : mardi 16 octobre 2012 - 15:10:54


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00437857, version 1


Marin Bertier, Yann Busnel, Anne-Marie Kermarrec. On Gossip and populations. 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2009), May 2009, Piran, Slovenia. 2009. 〈inria-00437857〉



Consultations de la notice


Téléchargements de fichiers