The P-Grid Project

External Publications Referring To P-Grid:

GRaSP: Generalized Range Search in Peer-to-peer Networks


We present a framework for generalized range search on trie-structured P2P networks, such as P-Grid. Our techniques exploit hitherto unknown properties of randomized tries. We prove that a P-Grid like network has routing diameter O(log n) with high probability, as well as O(log n) congestion, regardless of the shape of the underlying trie. Based on these properties, we propose GRaSP, a simple scheme for handling arbitrary range search problems, with search and update hop latency O(log n) with high probabil ity. We then apply GRaSP on two range search problems: multidimensional range search over points and rectangles, and three-sided search. Our empirical results show that GRaSP delivers excellent search performance and exhibits very good scalability under heavy load. With respect to three-sided search, our proposed scheme is distinguished in that it attempts to improve load balancing by introducing redundancy via the choice of search space.



Contention-Based Performance Evaluation of Multidimensional Range Search in Peer-to-peer Networks


Performance evaluation of peer-to-peer search techniques has been based on simple performance metrics, such as message hop counts and total network traffic, mostly disregarding their inherent concurrent nature, where contention may arise. This paper is concerned with the effect of con tention in complex P2P network search, focusing on techniques for multidimensional range search. We evaluate peer- to-peer networks derived from recently proposed works, introducing two novel metrics related to concurrency and contention, namely responsiveness and throughput. Our results highlight the impact of contention on these networks, and demonstrate that some studied networks do not scale in the presence of contention. Also, our results indicate that certain network properties believed to be desirable (e.g. uniform data distribution or peer accesses) may not be as critical as previously believed.