P2P overlays based on Delaunay triangulations have been recently exploited to implement systems providing efficient routing and data broadcast solutions. Several applications such as Distributed Virtual Environments and geographical nearest neighbours selection benefit from this approach. This paper presents a novel distributed algorithm for the incremental construction of a Delaunay overlay in a P2P network. The algorithm employs a distributed version of the classical Edge Flipping procedure. Each peer builds the Delaunay links incrementally by exploiting a random peer sample returned by the underlying gossip level. The algorithm is then optimized by considering the Euclidean distance between peers to speed up the overlay convergence. We present theoretical results that prove the correctness of our approach along with a set of experiments that assess the convergence rate of the distributed algorithm.
GoDel: Delaunay overlays in P2P networks via Gossip
Baraglia R;Dazzi P;
2012
Abstract
P2P overlays based on Delaunay triangulations have been recently exploited to implement systems providing efficient routing and data broadcast solutions. Several applications such as Distributed Virtual Environments and geographical nearest neighbours selection benefit from this approach. This paper presents a novel distributed algorithm for the incremental construction of a Delaunay overlay in a P2P network. The algorithm employs a distributed version of the classical Edge Flipping procedure. Each peer builds the Delaunay links incrementally by exploiting a random peer sample returned by the underlying gossip level. The algorithm is then optimized by considering the Euclidean distance between peers to speed up the overlay convergence. We present theoretical results that prove the correctness of our approach along with a set of experiments that assess the convergence rate of the distributed algorithm.File | Dimensione | Formato | |
---|---|---|---|
prod_212313-doc_78253.pdf
solo utenti autorizzati
Descrizione: GoDel: Delaunay overlays in P2P networks via Gossip
Tipologia:
Versione Editoriale (PDF)
Dimensione
1.21 MB
Formato
Adobe PDF
|
1.21 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.