Scalable blind search and broadcasting over Distributed Hash Tables

Typical blind search algorithms in P2P networks generate a significant amount of duplicate query messages in order to increase the success rate. We present a novel framework, named Recursive Partitioning Search (RPS), for blind search over structured peer-to-peer (P2P) networks, by which the query message duplication can be avoided. Two realizations of the framework for Chord and Pastry are presented. By simulation, we compare success rate, lookup delay and overlay network load of RPS with various well-known blind search algorithms, and illustrate RPS being a superior blind search algorithm running over DHTs. The algorithm guarantees that with high probability the lookup delay to visit every peer is of O(log N) hops, comparable to the delay of the exact-match search over the DHTs, which is proved for two example DHTs, Chord and Pastry in the paper. RPS is a simple and intuitive method for blind search over DHTs compared to other complex approaches like those building sophisticated index structures or requiring analysis of the words in the stored documents, yet a lot more efficient than known simple methods like Flooding and Random Walk. With RPS, every node in the overlay network is visited not more than once by design. These characteristics qualify the Recursive Partitioning Search over DHT as an efficient broadcasting algorithm. We investigate RPS scalability and propose a formula to choose an appropriate Time-to-Live (TTL) parameter value to maintain the balance between high success rate and reasonable network load. Active peer churn degrades the performance of RPS as a broadcasting mechanism proportionally to the churn rate. But the success rate of blind search using RPS may be affected negligibly if proper replications exist as in most P2P file sharing networks.