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 Network via Gossip

Ricci, Laura;Dazzi, Patrizio;Guidi, Barbara
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.
9781467328616
File in questo prodotto:
File Dimensione Formato  
GoDel_Delaunay Overlays in P2P Networks.pdf

solo utenti autorizzati

Tipologia: Versione finale editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/154102
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 41
social impact