Fast Generation and Mixing of Random Graphs in Peer-to-Peer Networks
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| dc.contributor.author | BEAUMONT, Olivier | |
| hal.structure.identifier | Institute of Mathematics and Computer Science [Wroclaw] [IMCS] | |
| dc.contributor.author | DOJWA, Marcin | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| dc.contributor.author | DUCHON, Philippe | |
| hal.structure.identifier | Institute for Computer Science | |
| dc.contributor.author | ELSÄSSER, Robert | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| dc.contributor.author | KLASING, Ralf | |
| hal.structure.identifier | Institute of Mathematics and Computer Science | |
| dc.contributor.author | KORZENIOWSKI, Miroslaw | |
| dc.date.accessioned | 2024-04-15T09:46:51Z | |
| dc.date.available | 2024-04-15T09:46:51Z | |
| dc.date.created | 2011-10-01 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198045 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.subject.en | peer-to-peer | |
| dc.subject.en | distributed hash tables | |
| dc.subject.en | heterogeneous p2p | |
| dc.subject.en | random graph generation and mixing | |
| dc.title.en | Fast Generation and Mixing of Random Graphs in Peer-to-Peer Networks | |
| dc.type | Document de travail - Pré-publication | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| hal.identifier | inria-00628312 | |
| hal.version | 1 | |
| hal.audience | Non spécifiée | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00628312v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=BEAUMONT,%20Olivier&DOJWA,%20Marcin&DUCHON,%20Philippe&ELS%C3%84SSER,%20Robert&KLASING,%20Ralf&rft.genre=preprint |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||