| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Heterogenous dating service with application to rumor spreading
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.
Cited literature [8 references]
https://hal.inria.fr/inria-00142778
Contributor : Olivier Beaumont <>
Submitted on : Monday, May 7, 2007 - 8:50:10 PM
Last modification on : Thursday, January 9, 2020 - 9:56:10 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 1:37:45 PM
Contributor : Olivier Beaumont <>
Submitted on : Monday, May 7, 2007 - 8:50:10 PM
Last modification on : Thursday, January 9, 2020 - 9:56:10 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 1:37:45 PM
File
datingservice.pdf
Files produced by the author(s)