an efficient, fault-tolerant and self organizing overlay using gossip-based construction and skip-lists principles

This paper presents GosSkip, a self organizing and fully dis-tributed 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, fair-ness and good behavior of the protocol under churn, while pre-serving the simplicity of the approach and maintaining O(log(N)) state per peer and O(log(N)) routing costs. In addition, we pro-pose 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 ex-periments with an actual implementation and real traces of a peer to peer workload