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

Métadonnées

Licence d’utilisation du document

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]

Langue

Document de travail - Pré-publication

Résumé en anglais

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.< Réduire

Mots clés en anglais

peer-to-peer

distributed hash tables

heterogeneous p2p

random graph generation and mixing

Métadonnées

Partager cette publication !

Licence d’utilisation du document

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

Langue

Résumé en anglais

Mots clés en anglais

URI

Origine

Unités de recherche