Heterogenous dating service with application to rumor spreading

Olivier Beaumont 1, 2 Philippe Duchon 1, 2 Miroslaw Korzeniowski 2
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.
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/inria-00142778
Contributor : Olivier Beaumont <>
Submitted on : Monday, May 7, 2007 - 8:50:10 PM
Last modification on : Friday, April 19, 2019 - 3:24:48 PM
Long-term archiving on : Tuesday, September 21, 2010 - 1:37:45 PM

File

datingservice.pdf
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

309

Files downloads

342