LARAS: locality aware replication algorithm for the Skip Graph

Abstract

Skip Graph, a member of the distributed hash table (DHT) family, has several benefits as an underlying structure in peer-to-peer (P2P) storage systems. In such systems, replication plays a key role on the system's performance. The traditional decentralized replication algorithms do not consider the locations of Skip Graph nodes in the network. Negligence of node locations in the placement of the replicas results in high access delays between the nodes and their closest replicas. This negatively affects the performance of the whole storage system. In this paper, with the aim of making Skip Graph's replication locality aware, we propose dynamic fully decentralized LARAS approach, where the data owner can replicate itself based on the system size, possible data requester nodes' set and using local information of the storage system. Our extensive performance results show that LARAS improves replication access delay of the Skip Graph based storage system about 20% and 38% in comparison to the best known decentralized counterpart in the public and private replication scenarios, respectively.