Skip to Main content Skip to Navigation
New interface
Conference papers

D2HT: the best of both worlds, Integrating RPS and DHT

Marin Bertier 1 François Bonnet 1 Anne-Marie Kermarrec 1 Vincent Leroy 1 Sathya Peri 1 Michel Raynal 1 
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : Distributed Hash Tables (DHTs) and Random Peer Sampling (RPS) provide important and complementary services in the area of P2P overlay networks. DHTs achieve efficient lookup while RPS enables nodes to build and maintain connectivity in the presence of high churn. Clearly, many applications, e.g. in the area of search, would greatly benefit if both these services were available together at a reasonable cost. This paper integrates a structured P2P overlay and a Random Peer Sampling service through gossip protocols. This system called D2HT, leverages the small-world nature of DHTs and relies on two cohabiting gossip protocols maintaining the close and long-range links respectively. The long links are chosen according to a harmonic distribution, following the Kleinberg small-world model. This approach exhibits several benefits: (i) The resulting DHT is highly dynamic and self-stabilizing, changes are tracked for free through the gossip nature of the protocol. This removes the need for complex, usually disjoint, and expensive join and repair procedures. Yet, it achieves reasonable routing performance with respect to standard DHTs; (ii) The resulting peer sampling service provides a biased sampling following a harmonic distribution: this improves the routing without jeopardizing the quality of the RPS. The set of long-range links which are a source of RPS can be used independently by others applications for free. They change continuously, achieving well-balanced routing across the nodes. We perform extensive simulations and compare the performances of D2HT with Cyclon, HRing, Symphony and Pastry to demonstrate the gains achieved by the approach proposed in this paper.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Vincent Leroy Connect in order to contact the contributor
Submitted on : Thursday, February 25, 2010 - 3:36:32 PM
Last modification on : Thursday, January 20, 2022 - 4:20:30 PM
Long-term archiving on: : Thursday, October 18, 2012 - 4:05:18 PM


Files produced by the author(s)


  • HAL Id : inria-00459944, version 1


Marin Bertier, François Bonnet, Anne-Marie Kermarrec, Vincent Leroy, Sathya Peri, et al.. D2HT: the best of both worlds, Integrating RPS and DHT. European Dependable Computing Conference, Apr 2010, Valencia, Spain. ⟨inria-00459944⟩



Record views


Files downloads