Gossip-Based Counting in Dynamic Networks

Abstract : We propose Gossipico, a gossip algorithm to average, sum or find minima and maxima over node values in a large, distributed, and dynamic network. Unlike previous work, Gossipico provides a continuous estimate of, for example, the number of nodes, even when the network becomes disconnected. Gossipico converges quickly due to the introduction of a beacon mechanism that directs messages to an autonomously selected beacon node. The information spread through the network shows a percolation-like phase-transition and allows information to propagate along near-shortest paths. Simulations in various different network topologies (ranging in size up to one million nodes) illustrate Gossipico’s robustness against network changes and display a near-optimal count time. Moreover, in a comparison with other related gossip algorithms, Gossipico displays an improved and more stable performance over various classes of networks.
Type de document :
Communication dans un congrès
Robert Bestak; Lukas Kencl; Li Erran Li; Joerg Widmer; Hao Yin. 11th International Networking Conference (NETWORKING), May 2012, Prague, Czech Republic. Springer, Lecture Notes in Computer Science, LNCS-7290 (Part II), pp.404-417, 2012, NETWORKING 2012. 〈10.1007/978-3-642-30054-7_32〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01531972
Contributeur : Hal Ifip <>
Soumis le : vendredi 2 juin 2017 - 11:23:30
Dernière modification le : samedi 18 novembre 2017 - 18:16:02
Document(s) archivé(s) le : mercredi 13 décembre 2017 - 09:17:32

Fichier

978-3-642-30054-7_32_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Ruud Bovenkamp, Fernando Kuipers, Piet Mieghem. Gossip-Based Counting in Dynamic Networks. Robert Bestak; Lukas Kencl; Li Erran Li; Joerg Widmer; Hao Yin. 11th International Networking Conference (NETWORKING), May 2012, Prague, Czech Republic. Springer, Lecture Notes in Computer Science, LNCS-7290 (Part II), pp.404-417, 2012, NETWORKING 2012. 〈10.1007/978-3-642-30054-7_32〉. 〈hal-01531972〉

Partager

Métriques

Consultations de la notice

27

Téléchargements de fichiers

16