A Michael F. Schwartz 

T A Scalable, Non-Hierarchical Resource Discovery Mechanism Based
on Probabilistic Protocols 

R Technical Report CU-CS-474-90 

I Department of Computer Science, University of Colorado,
Boulder, Colorado 

D June 1990 

K Yellow pages, YP 

X Available from
ftp:ftp.cs.colorado.edupubcstechreportsschwartzProbYP or
ftp:ftp.cs.colorado.edupubcstechreportsschwartzProbYP.txt.Z 

X Abstract:  "Computer network interconnection provides access to
a bewildering array of resources, including databases, network
services, and people in various capacities.  We consider the
problem of allowing users to discover the existence of such
resources in a large scale, administratively decentralized
environment.  While hierarchically organized resource registries
have good scalability properties, they provide poor support for
resource discovery, because users must understand how the nested
components are arranged.  In this paper we present a
probabilistic approach that supports non-hierarchical, attribute
based "yellow pages" searches.  The protocols support locating a
small number of instances of moderately large classes of objects. 
The resource graph evolves over time in accordance with what
resources exist and the types of searches that users make. 
Simulation results indicate that the approach can support
scalable and flexible resource discovery for an environment
roughly the size of a large couny, with several thousand
administrative domains participating in resource registration and
searches.  Moreover, the probabilistic search strategy naturally
supports fair access among competing information providers."