Skip to Main content Skip to Navigation
Conference papers

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
CNRS - Centre National de la Recherche Scientifique : UMR5800, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Inria Bordeaux - Sud-Ouest, Université Sciences et Technologies - Bordeaux 1
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 metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Olivier Beaumont Connect in order to contact the contributor
Submitted on : Monday, May 7, 2007 - 8:50:10 PM
Last modification on : Tuesday, February 9, 2021 - 3:00:04 PM
Long-term archiving on: : Tuesday, September 21, 2010 - 1:37:45 PM


Files produced by the author(s)




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⟩



Record views


Files downloads