Heterogenous dating service with application to rumor spreading

Olivier Beaumont 1, 2 Philippe Duchon 1, 2 Miroslaw Korzeniowski 2
1 LaBRI - Laboratoire Bordelais de Recherche en Informatique
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : In this paper, we describe a fully decentralized algorithm, called "dating service" to organize communications into a fully heterogeneous network, that ensures that communication capabilities of the nodes are not exceeded. We prove that with high probability, this service ensures that a constant fraction of all possible communications is organized. Interestingly enough, this property holds true even if a node is not able to choose another node uniformly at random. We also present, as an application of the dating service, an algorithm for rumor spreading that enables to broadcast a unit-size message to all the nodes of a P2P system in logarithmic number of steps with high probability.
Keywords : randomized algorithms distributed algorithms rumor spreading heterogeneous platforms
Type de document :
Communication dans un congrès
IEEE International Symposium on Parallel and Distributed Processing, 2008. IPDPS 2008., Apr 2008, Miami, FL, United States. IEEE, pp 1--10, 2008, IPDPS Proceedings. 〈10.1109/IPDPS.2008.4536294〉
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00142778
Contributeur : Olivier Beaumont <>
Soumis le : lundi 7 mai 2007 - 20:50:10
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : mardi 21 septembre 2010 - 13:37:45

Fichier

datingservice.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | INRIA-RRRT | LABRI | RRLABRI | UNIV-BORDEAUX | INRIA-BORDEAUX

Citation

Olivier Beaumont, Philippe Duchon, Miroslaw Korzeniowski. Heterogenous dating service with application to rumor spreading. IEEE International Symposium on Parallel and Distributed Processing, 2008. IPDPS 2008., Apr 2008, Miami, FL, United States. IEEE, pp 1--10, 2008, IPDPS Proceedings. 〈10.1109/IPDPS.2008.4536294〉. 〈inria-00142778v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

296

Téléchargements de fichiers

151

Contact


archive-ouverte@inria.fr