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
Rapport (Rapport De Recherche) Année : 2007

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 (336.28 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

  • HAL Id : inria-00142778 , version 1

Citer

Olivier Beaumont, Philippe Duchon, Miroslaw Korzeniowski. Heterogenous dating service with application to rumor spreading. [Research Report] RR-6168, 2007. ⟨inria-00142778v1⟩

Collections

INRIA-RRRT
135 Consultations
178 Téléchargements

Partager

Gmail Facebook X LinkedIn More