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

Olivier Beaumont 1, 2 Marcin Dojwa 3 Philippe Duchon 1, 2 Robert Elsässer 4 Ralf Klasing 1, 2 Miroslaw Korzeniowski 5
1 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : 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.
Type de document :
Pré-publication, Document de travail
2011
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00628312
Contributeur : Olivier Beaumont <>
Soumis le : samedi 1 octobre 2011 - 22:28:20
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : lundi 2 janvier 2012 - 02:21:14

Fichier

mixing.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00628312, version 1

Collections

Citation

Olivier Beaumont, Marcin Dojwa, Philippe Duchon, Robert Elsässer, Ralf Klasing, et al.. Fast Generation and Mixing of Random Graphs in Peer-to-Peer Networks. 2011. 〈inria-00628312〉

Partager

Métriques

Consultations de la notice

261

Téléchargements de fichiers

178