PLATON: Peer-to-Peer load adjusting tree overlay networks

Peer-to-Peer systems supporting multi attribute and range queries use a number of techniques to partition the multi dimensional data space among participating peers. Load-balancing of data accross peer partitions is necessary in order to avoid the presence of network hotspots which may cause performance degradation or failures within the distributed environment. In this paper, we introduce a novel framework, PLATON, that preserves load balancing accross peer partitions when the multi-dimensional data space is dynamic, without requiring up-to-date global load information, e.g. information about the most loaded or least loaded peers in the network. A theoretical analysis on the upper bounds (ie. worst case) of the proposed algorithm is presented; its performance is evaluated in large-scale simulated networks and validated within in the PlanetLab emulation platform