Skip to Main content Skip to Navigation
New interface
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
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 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 : Saturday, June 25, 2022 - 8:30:03 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