Supporting Data Currency in Replicated DHTs using a Keybased Timestamping Service

Reza Akbarinia 1 Esther Pacitti 2 Patrick Valduriez 1, 3
1 ATLAS - Complex data management in distributed systems
UN - Université de Nantes, Inria Rennes – Bretagne Atlantique
2 ZENITH - Scientific Data Management
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Distributed Hash Tables (DHTs) provide a scalable solution for data sharing in P2P systems. To ensure high data availability, DHTs typically rely on data replication, yet without data currency guarantees. Supporting data currency in replicated DHTs is difficult as it requires the ability to return a current replica despite peers leaving the network or concurrent updates. In this paper, we give a complete solution to this problem. We propose an Update Management Service (UMS) to deal with data availability and efficient retrieval of current replicas based on timestamping. For generating timestamps, we propose a Key-based Timestamping Service (KTS) which performs distributed timestamp generation using local counters. Through probabilistic analysis, we compute the expected number of replicas which UMS must retrieve for finding a current replica. Except for the cases where the availability of current replicas is very low, the expected number of retrieved replicas is typically small, e.g. if at least 35% of available replicas are current then the expected number of retrieved replicas is less than 3. We validated our solution through implementation and experimentation over a 64-node cluster and evaluated its scalability through simulation up to 10,000 peers using SimJava. The results show the effectiveness of our solution. They also show that our algorithm used in UMS achieves major performance gains, in terms of response time and communication cost, compared with a baseline algorithm.
Type de document :
Communication dans un congrès
BDA: Bases de Données Avancées, Oct 2007, Marseille, France. 2007
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00482342
Contributeur : Reza Akbarinia <>
Soumis le : dimanche 17 juillet 2016 - 10:19:18
Dernière modification le : jeudi 24 mai 2018 - 15:59:21

Fichier

Supporting.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00482342, version 1

Citation

Reza Akbarinia, Esther Pacitti, Patrick Valduriez. Supporting Data Currency in Replicated DHTs using a Keybased Timestamping Service. BDA: Bases de Données Avancées, Oct 2007, Marseille, France. 2007. 〈inria-00482342〉

Partager

Métriques

Consultations de la notice

215

Téléchargements de fichiers

33