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.
Liste complète des métadonnées

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00436689
Contributor : Kévin Huguenin <>
Submitted on : Thursday, March 14, 2013 - 3:45:50 PM
Last modification on : Thursday, November 15, 2018 - 11:57:35 AM
Document(s) archivé(s) le : Saturday, June 15, 2013 - 2:35:07 AM

File

PaperP2P.pdf
Files produced by the author(s)

Identifiers

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. ⟨10.1109/P2P.2006.19⟩. ⟨inria-00436689⟩

Share

Metrics

Record views

833

Files downloads

250