As a distributed hash table (DHT) routing overlay, Skip Graph is used in a variety of peer-to-peer (P2P) systems including cloud storage. The overlay connectivity of P2P systems is negatively affected by the arrivals and departures of nodes to and from the system that is known as churn. Preserving connectivity of the overlay network (i.e., the reachability of every pair of nodes) under churn without compromising the overlay latency is a performance challenge in every P2P system including the Skip Graph-based ones. The existing decentralized churn stabilization solutions that are applicable to Skip Graphs mainly optimize the connectivity of the system under churn and do not consider routing latency of overlay as an optimization goal. Additionally, those existing solutions change the message complexity of Skip Graphs, distort its topology, or apply constant message overhead to the system. In this paper, we propose Interlaced , a fully decentralized churn stabilization mechanism for Skip Graphs that provides drastically stronger overlay connectivity and faster search queries without changing the asymptotic complexity of the Skip Graph in terms of storage, computation, and communication. We also propose the Sliding Window De Bruijn Graph (SWDBG ) as a tool to predict the availability of nodes with high accuracy. Our simulation results show that in comparison to the best existing DHT-based solutions, Interlaced improves the overlay connectivity of the Skip Graph under churn with the gain of about 1.73 times. Likewise, compared to the existing availability prediction approaches for P2P systems, SWDBG is about 1.26 times more accurate. A Skip Graph that benefits from Interlaced and SWDBG is about 2.47 times faster on average in routing the queries under churn compared to the best existing solutions. We also present an adaptive extension of Interlaced to be applied to other DHTs, for example, Kademlia.

As an append-only distributed database, blockchain is utilized in a vast variety of applications including the cryptocurrency and Internet-of-Things (IoT). The existing blockchain solutions show downsides in communication and storage scalability, as well as decentralization. In this article, we propose LightChain, which is the first blockchain architecture that operates over a Distributed Hash Table (DHT) of participating peers. LightChain is a permissionless blockchain that provides addressable blocks and transactions within the network, which makes them efficiently accessible by all peers. Each block and transaction is replicated within the DHT of peers and is retrieved in an on-demand manner. Hence, peers in LightChain are not required to retrieve or keep the entire ledger. LightChain is fair as all of the participating peers have a uniform chance of being involved in the consensus regardless of their influence such as hashing power or stake. We provide formal mathematical analysis and experimental results (simulations and cloud deployment) to demonstrate the security, efficiency, and fairness of LightChain, and show that LightChain is the only existing blockchain that can provide integrity under the corrupted majority power of peers. As we experimentally demonstrate, compared to the mainstream blockchains such as Bitcoin and Ethereum, LightChain requires around 66 times smaller per node storage, and is around 380 times faster on bootstrapping a new node to the system, and each LightChain node is rewarded equally likely for participating in the protocol.

Skip Graphs belong to the family of Distributed Hash Table (DHT) structures that are utilized as routing overlays in various peer-to-peer applications including blockchains, cloud storage, and social networks. In a Skip Graph overlay, any misbehavior of peers during the routing of a query compromises the system functionality. Guard is the first authenticated search mechanism for Skip Graphs, enables reliable search operation in a fully decentralized manner. In this demo paper, we present a proof-of-concept implementation of Guard on Skip Graph nodes as well as a deployment demo scenario.

Skip Graphs are Distributed Hash Table (DHT)based data structures that are immensely utilized as routing overlays in Peer-to-Peer (P2P) applications. In this demo paper, we present the software architecture of our open-source implementation of Skip Graph middleware in Java. We also present a demo scenario on configuration and constructing an overlay of Skip Graph processes in a fully decentralized manner. Our implementation is capable of hosting data objects at the Skip Graph processes and serving as a P2P data storage platform as well. Our middleware implementation provides an open-source platform to support Skip Graph-based applications on top of it.

As a Distributed Hash Table (DHT), Skip Graph routing overlays are exploited in several peer-to-peer (P2P) services, including P2P cloud storage. The fully decentralized replication algorithms that are applicable to the Skip Graph-based P2P cloud storage fail on improving the performance of the system with respect to both the availability of replicas as well as their response time. Additionally, they presume the system as homogeneous with respect to the nodes' latency distribution, availability behavior, and bandwidth, or storage. In this article, we propose Pyramid, which is the first fully decentralized utility- and locality-aware replication approach for Skip Graph-based P2P cloud storage systems. Pyramid considers the nodes as heterogeneous with respect to their latency distribution, availability behavior, bandwidth, and storage. Pyramid is utility-aware as it maximizes the average available bandwidth of replicas per time slot (e.g., per hour). Additionally, Pyramid is locality-aware as it minimizes the average latency between nodes and their closest replica. Our simulation results show that compared to the state-of-the-art solutions that either perform good in utility-awareness, or in locality-awareness, our proposed Pyramid improves both the utility- and locality-awareness of replicas with a gain of about 1.2 and 1.1 times at the same time, respectively.

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.