Abstract
A scalable and expressive peer-to-peer (P2P) networking and computing framework requires efficient resource discovery services. Here we propose NEVRLATE, for Network-Efficient Vast Resource Lookup At The Edge, an efficient organization of directories or directory mirrors, providing a scalable distributed resource discovery service. NEVRLATE organizes directory servers in an approximate two-dimensional grid, or a set of sets of servers, for registration to occur in one 'horizontal' dimension, and lookup to occur in the other 'vertical' dimension. The payoff of organizing n servers into a structure like this is to achieve O(pn) message complexity for registration, and nearly constant complexity lookup. At extra cost NEVRLATE can provide fault tolerance, high availability and security, anonymity, and privacy. The protocol described can be seen as a way to organize Gnutella supernodes, or as a performance extension of Freenet's architecture. In addition, it supports expressive lookup mechanisms, and may provide a basis for a truly scalable worldwide infrastructure for the semantic and the extended web.