Probabilistic Scalable P2P Resource Location Services

Scalable resource discovery services form the core of directory and other middleware services. Scalability requirements preclude centralized solutions. The need to have directory services that are highly robust and that can scale with the number of resources and the performance of individual nodes, points to Peer-to-Peer (P2P) architectures as a promising approach. The resource location problem can be simply stated as "given a resource name, find the location of a node or nodes that manage the resource." We call this the deterministic location problem. In a very large network, it is clearly not feasible to contact all nodes to locate a resource. Therefore, we modify the problem statement to "given a resource name, find with a given probability, the location of a node or nodes that manage the resource." We call this a probabilistic location approach. We present a protocol that solves this problem and develop an analytical model to compute the probability that a directory entry is found, the fraction of peers involved in a search, and the average number of hops required to find a directory entry. Numerical results clearly show that the proposed approach achieves high probability of finding the entry while involving a relatively small fraction of the total number of peers. The analytical results are further validated by results obtained from an implementation of the proposed protocol in a cluster of workstations