Analysis in Heterogeneous Distributed Hash Tables
Cvvn Varun, A Siddhartha Reddy, V. Siva, Nagi Reddy, Sivakanth Gopi · 2012
We present a scheme for evenly partitioning the key space in distributed hash tables among the participating nodes. The scheme is based on the multiple random choices paradigm and handles both node joins and leaves. It achieves, with high probability, a ratio of at most 4 between the loads of the most and least burdened nodes, in the face or arbitrary node arrivals and departures. Each join or leave operation incurs message cost that is, with high probability, O (log 2 n), where n is the number of nodes, and causes the re location of keys from at most one node (for joins) or three nodes (for leaves).In this paper, A version of heterogeneous systems, where the capacities of nodes to serve keys can vary widely.