GosSkip, an Efficient, Fault-tolerant and Self Organizing Overlay using Gossip-based Construction and Skip-lists Principles

Rachid Guerraoui 1, 2 Sidath Handurukande 2, 1 Kévin Huguenin 3 Anne-Marie Kermarrec 4 Fabrice Le Fessant 5 Rivière Étienne 4
3 PARIS - Programming distributed parallel systems for large scale numerical simulation
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, ENS Cachan - École normale supérieure - Cachan, Inria Rennes – Bretagne Atlantique
4 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
5 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
UR1 - Université de Rennes 1, Inria Saclay - Ile de France, INSA - Institut National des Sciences Appliquées, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : This paper presents GosSkip, a self organizing and fully distributed overlay that provides a scalable support to data storage and retrieval in dynamic environments. The structure of GosSkip, while initially possibly chaotic, eventually matches a perfect set of Skip-list-like structures, where no hash is used on data attributes, thus preserving semantic locality and permitting range queries. The use of epidemic-based protocols is the key to scalability, fairness and good behavior of the protocol under churn, while preserving the simplicity of the approach and maintaining O(log(N)) state per peer and O(log(N)) routing costs. In addition, we propose a simple and efficient mechanism to exploit the presence of multiple data items on a single physical node. GosSkip's behavior in both a static and a dynamic scenario is further conveyed by experiments with an actual implementation and real traces of a peer to peer workload.
Type de document :
Communication dans un congrès
6th IEEE International Conference on Peer to Peer Computing (P2P), Sep 2006, Cambridge, United Kingdom. 2006, 〈10.1109/P2P.2006.19〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00436689
Contributeur : Kévin Huguenin <>
Soumis le : jeudi 14 mars 2013 - 15:45:50
Dernière modification le : mardi 21 novembre 2017 - 15:22:18
Document(s) archivé(s) le : samedi 15 juin 2013 - 02:35:07

Fichier

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

Identifiants

Citation

Rachid Guerraoui, Sidath Handurukande, Kévin Huguenin, Anne-Marie Kermarrec, Fabrice Le Fessant, et al.. GosSkip, an Efficient, Fault-tolerant and Self Organizing Overlay using Gossip-based Construction and Skip-lists Principles. 6th IEEE International Conference on Peer to Peer Computing (P2P), Sep 2006, Cambridge, United Kingdom. 2006, 〈10.1109/P2P.2006.19〉. 〈inria-00436689〉

Partager

Métriques

Consultations de la notice

477

Téléchargements de fichiers

178