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 metadatas

Cited literature [24 references]  Display  Hide  Download
Contributor : Olivier Beaumont <>
Submitted on : Saturday, October 1, 2011 - 10:28:20 PM
Last modification on : Thursday, July 26, 2018 - 3:20:10 PM
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. 2011. ⟨inria-00628312⟩



Record views


Files downloads