INFOCOM 2008. The 27th Conference on Computer Communications. IEEE
Several models of user churn, resilience, and link lifetime have recently appeared in the literature , , , ; however, these results do not directly apply to classical Distributed Hash Tables (DHTs) in which neighbor replacement occurs not only when current users die, but also when new user arrive into the system, and where replacement choices are often restricted to the successor of the failed zone in the DHT space. To understand neighbor churn in such networks, this paper proposes a simple, yet accurate, model for capturing link dynamics in structured P2P systems and obtains the distribution of link lifetimes for fairly generic DHTs. Similar to , our results show that deterministic networks (e.g., Chord , CAN ) unfortunately do not extract much benefit from heavy-tailed user lifetimes since link durations are dominated by small remaining lifetimes of newly arriving users that replace the more reliable existing neighbors. We also examine link lifetimes in randomized DHTs equipped with multiple choices for each link and show that users in such systems should prefer neighbors with smaller zones rather than larger age as suggested in prior work , . We finish the paper by demonstrating the effectiveness of the proposed min-zone neighbor selection for heavy-tailed user lifetime distributions with the shape parameter alpha obtained from recent measurements , .
Copyright © 2008 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.
Place of Publication
P2P networks, peer-to-peer, DHTs, Distributed Hash Tables, neighbor replacement, link lifetime, neighbor churn
Yao, Zhongmei and Loguinov, Dmitri, "Link Lifetimes and Randomized Neighbor Selection in DHTs" (2008). Computer Science Faculty Publications. 11.
Databases and Information Systems Commons, Numerical Analysis and Scientific Computing Commons, OS and Networks Commons, Other Computer Sciences Commons, Programming Languages and Compilers Commons, Theory and Algorithms Commons