BaRT, balanced randomized tree: A scalable and distributed protocol for lookup in peer-to-peer networks

This paper proposes a new scheme for p2p networks. The main contributions are an extensive use of randomization techniques and a novel usage of tree-data structure. The combination of these two ingredients allows a great flexibility of network parameters, such as: load balance among the peers, fast lookups and reduced memory usage. For instance, with routing tables of size $(d-1) log_d n$, the average number of hops for a lookup is of the order of $1/d((d-1) log_d n +1)$, where n is the number of peers in the network and d is the ariety of the tree data structure. Further, we propose a few new optimization mechanisms that can be adopted in DHT. Extensive simulations support these results.