Fast Generation and Mixing of Random Graphs in Peer-to-Peer Networks
BEAUMONT, Olivier
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
DUCHON, Philippe
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
See more >
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
BEAUMONT, Olivier
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
DUCHON, Philippe
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
KLASING, Ralf
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
< Reduce
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Language
en
Document de travail - Pré-publication
English 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 ...Read more >
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.Read less <
English Keywords
peer-to-peer
distributed hash tables
heterogeneous p2p
random graph generation and mixing
Origin
Hal imported