Treffer: Heterogenous dating service with application to rumor spreading

Title:
Heterogenous dating service with application to rumor spreading
Authors:
Beaumont, Olivier, Duchon, Philippe, Korzeniowski, Miroslaw
Contributors:
Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Centre Inria de l'Université de Bordeaux, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), IEEE, ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005)
Source:
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⟩
Publisher Information:
CCSD; IEEE, 2008.
Publication Year:
2008
Collection:
collection:CNRS
collection:INRIA
collection:ENSEIRB
collection:INRIA-BORDEAUX
collection:LABRI
collection:RRLABRI
collection:UNIV-BORDEAUX
collection:INRIA_TEST
collection:TESTALAIN1
collection:TESTBORDEAUX
collection:INRIA2
collection:ANR
collection:UNIVERSITE-BORDEAUX
Subject Terms:
randomized algorithms, distributed algorithms rumor spreading heterogeneous platforms, [INFO.INFO-DC]Computer Science [cs], Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-DS]Computer Science [cs], Data Structures and Algorithms [cs.DS]
Subject Geographic:
Miami, FL, United States
Original Identifier:
HAL:
Document Type:
Konferenz conferenceObject<br />Conference papers
Language:
English
Relation:
info:eu-repo/semantics/altIdentifier/doi/10.1109/IPDPS.2008.4536294
DOI:
10.1109/IPDPS.2008.4536294
Access URL:
https://inria.hal.science/inria-00142778
https://inria.hal.science/inria-00142778v2/document
https://inria.hal.science/inria-00142778v2/file/datingservice.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00142778v2
Database:
HAL

Weitere Informationen

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.