Results

The following summarizes our experimental results:

• In Section VI-A, we show that simple namespace balancing is effective when workloads are uniform and node capacities are a constant (its assumed conditions). We portray the diminished value in this form of balancing as workload becomes skewed.

• In Section VI-B, we explore parameter choices for $\kappa$ for k-Choices and find that $\kappa = 8$ performs well for the workloads we examine.

• In Section VI-C, we compare how the algorithms respond to varying applied workload when nodes follow trace-based churn and capacity. We find that only k-Choices and Transfer can support large amounts of skewed load.

• We show that k-Choices can support high churn rates in Section VI-D.

• Section VI-E portrays that k-Choices sustains high success rates throughout shifting workloads. We also find that Transfer, Threshold, Proportion exhibit inconsistent results over time.

• In Section VI-F, we show that none of the algorithms can support very skewed workloads (e.g., $\alpha=4.8$) and that they increase in variance as skew increases.

• In Section VI-G, we find our implementation of k-Choices within Pastry [38] improves throughput by $20\%$ on an implementation in a heterogeneous-bandwidth networked environment.

More information on the experiments, simulator, tuning, and validation is available in the accompanying technical report [27].