Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Olivier Beaumont Connect in order to contact the contributor
Submitted on : Saturday, October 1, 2011 - 10:28:20 PM
Last modification on : Saturday, June 25, 2022 - 10:32:40 AM
Long-term archiving on: : Monday, January 2, 2012 - 2:21:14 AM


Files produced by the author(s)


  • HAL Id : inria-00628312, version 1



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. {date}. ⟨inria-00628312⟩



Record views


Files downloads