2019/03/18 by Yahya Hassanzadeh-Nazarabadi, Alptekın Küpçü, Hassanzadeh-Nazarabadi, Yahya +3 · 1 citation
Computer Science · #Caching and Content Delivery #Distributed #FOS: Computer and information sciences #Parallel #Peer-to-Peer Network Technologies #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1903.07289
openalex publication_date 2019/03/18 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
As a distributed hash table (DHT) routing overlay, Skip Graph is used in a\nvariety of peer-to-peer (P2P) systems including cloud storage, social networks,\nand search engines. The overlay connectivity of P2P systems is negatively\naffected by the arrivals and departures of nodes to and from the system that is\nknown as churn. Preserving connectivity of the overlay network (i.e., the\nreachability of every pair of nodes) under churn is a performance challenge in\nevery P2P system including the Skip Graph-based ones. The existing\ndecentralized churn stabilization solutions that are applicable on Skip Graphs\nhave intensive communication complexities, which leave them unable to provide a\nstrong overlay connectivity, especially under high rates of churn.\n In this paper, we propose Interlaced, a fully decentralized churn\nstabilization mechanism for Skip Graphs that provides drastically stronger\noverlay connectivity without changing the asymptotic complexity of the Skip\nGraph in terms of storage, computation, and communication. We also propose the\nSliding Window De Bruijn Graph (SW-DBG) as a tool to predict the availability\nof nodes with high accuracy. Our simulation results show that in comparison to\nthe best existing DHT-based solutions, Interlaced improves the overlay\nconnectivity of Skip Graph under churn with the gain of about 1.81 times. A\nSkip Graph that benefits from Interlaced and SW-DBG is about 2.47 times faster\non average in routing the queries under churn compared to the best existing\nsolutions. We also present an adaptive extension of Interlaced to be applied on\nother DHTs, for example Kademlia.\n