Speaker: Junning Liu
<br>
<br>
Title: Load Balancing in Hypercubic Distributed Hash Tables with
Heterogeneous Nodes
<br>
<br>

Recent research has seen considerable work on load balancing for
distributed hash tables (DHTs), a fundamental tool in Peer-to-Peer
networks.  Previous work in this area makes the assumption of
homogeneous nodes, where each node has the same power (CPU, memory,
network bandwidth, etc.).  Here, we study load balancing strategies
for hypercubic DHTs in an environment where processors have different
capabilities.  In particular, we assume that each processor has a
size, which represents its resource capabilities.  We give a fairness
criteria based on minimizing the difference between the processors of
the ratio of the fraction of the DHT address space stored on a
processor to the size of the processor.  For the offline problem, we
give a polynomial time algorithm that finds the optimal partitioning
of the address space between the processors.  We also study the online
problem.  With an adversary, we give a lower bound on the competitive
ratio for online algorithms for this problem. We also describe an
algorithm with performance very close to the competitive ratio of the
lower bound.
<br>
<br>
Joint work with Micah Adler