BEAUMONT, Olivier; DUCHON, Philippe; KORZENIOWSKI, Miroslaw

doi:10.1109/IPDPS.2008.4536294

Metadatos

Licencia de uso del documento

BEAUMONT, Olivier
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

DUCHON, Philippe
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

KORZENIOWSKI, Miroslaw
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

Idioma

Communication dans un congrès

Este ítem está publicado en

IEEE International Symposium on Parallel and Distributed Processing, 2008. IPDPS 2008., 2008-04-15, Miami, FL. 2008p. pp 1--10

IEEE

Resumen en inglés

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.< Leer menos

Palabras clave en inglés

randomized algorithms

distributed algorithms rumor spreading heterogeneous platforms

URI

https://oskar-bordeaux.fr/handle/20.500.12278/198862

DOI

http://dx.doi.org/10.1109/IPDPS.2008.4536294

Proyecto ANR

ALgorithmique des Plates-formes A Grande Echelle - ANR-05-MMSA-0006

Orígen

Importado de Hal

Centros de investigación

Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800