Heterogenous dating service with application to rumor spreading - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

Heterogenous dating service with application to rumor spreading

Résumé

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.
Fichier principal
Vignette du fichier
datingservice.pdf (334.79 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00142778 , version 1 (22-04-2007)
inria-00142778 , version 2 (07-05-2007)

Identifiants

Citer

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., IEEE, Apr 2008, Miami, FL, United States. pp 1--10, ⟨10.1109/IPDPS.2008.4536294⟩. ⟨inria-00142778v2⟩
135 Consultations
178 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More