BEAUMONT, Olivier; DOJWA, Marcin; DUCHON, Philippe; ELSÄSSER, Robert; KLASING, Ralf; KORZENIOWSKI, Miroslaw

Metadatos

Licencia de uso del documento

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

DOJWA, Marcin
Institute of Mathematics and Computer Science [Wroclaw] [IMCS]

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

Idioma

Document de travail - Pré-publication

Resumen en inglés

In this work we show how to quickly generate and rapidly mix uniform random graphs in a model where incoming and outgoing degrees of nodes are defined in advance. We show how to use a previous result on Dating Service working on top of any Distributed Hash Table so that a random graph is generated in logarithmic number of rounds and mixed so that two snapshots of the graph taken in logarithmic time distance are independent with high probability. We consider two models of graphs: directed graphs and undirected graphs where some nodes are behind firewalls. We consider a synchronized model of computation but show how to adapt it to a highly dynamic and asynchronous environment such as peer-to-peer networks.< Leer menos

Palabras clave en inglés

peer-to-peer

distributed hash tables

heterogeneous p2p

random graph generation and mixing

Metadatos

Compartir este ítem

Licencia de uso del documento

Fast Generation and Mixing of Random Graphs in Peer-to-Peer Networks

Idioma

Resumen en inglés

Palabras clave en inglés

URI

Orígen

Centros de investigación