With the notion of virtual servers, peers participating in a distributed hash table (DHT) may host different numbers of virtual servers and are enabled to balance their loads in the reallocation of virtual servers. While most decentralized load balance algorithms designed for the DHTs based on virtual servers offer no performance guarantees, we present in this paper a novel distributed load balancing algorithm for DHTs with stochastic performance bounds. In addition to rigorous performance analysis, we compare our proposal with competitive algorithms through computer simulations. The simulation results indicate that our proposal clearly outperforms the previous algorithms.