@device(postscript)
@libraryfile(Mathematics10)
@libraryfile(Accents)
@style(fontfamily=timesroman,fontscale=11)
@pagefooting(immediate, left "@c<Technical Report 1996>",
center "@c<Computer Science>",
right "@c<Carnegie Mellon>")
@heading(Using Dynamic Sets to Reduce the Aggregate Latency of Data Access)
@heading(CMU-CS-96-194)
@center(@b(David Cappers Steere))
@center(November 1996 - Ph.D. Thesis)
@center(FTP: Unavailable)
@blankspace(1)
@begin(text)

Many users of large distributed systems are plagued by high latency when
accessing remote data.  Latency is particularly problematic for the critical
application of search and retrieval, which tends to access many objects
and may suffer a long wait for each object accessed.  Existing techniques like
caching, inferential prefetching, and explicit prefetching are not suited to
search, are ineffective at reducing latency for search applications, or
greatly increase the complexity of the programming model.  This
dissertation shows that extending the file system interface to support a new
abstraction called @i(dynamic sets) can address the problem of latency for
search without incurring the penalties of the other techniques.

A dynamic set is a lightweight and transitory collection of objects with
well-defined semantics.  An application creates a dynamic set on-demand to 
hold the objects it wishes to process.  Adding dynamic sets to the system's
interface results in two benefits.  First, creation of a set discloses
the application's interest in the set's members to the system.  This allows
the system to reduce the aggregate I/O latency of search through prefetching
and reordering of requests.  Second, dynamic sets provide direct support
for accessing and manipulating sets of objects.  Thus dynamic sets improve
performance and functionality without unduly increasing the complexity of the
programming model.

This dissertation describes the design of the dynamic sets abstraction, an
implementation which adds dynamic sets to the 4.3 BSD file system interface,
and an evaluation of the implementation.  The implementation allows several
applications, including Unix search tools and a WWW browser, to access 
sets of Coda, NFS, WWW, and local file system objects.  With little effort
one can modify other applications to use sets or extend the implementation
to allow access to other systems.  The evaluation shows that dynamic
sets can substantially reduce I/O latency for search on wide and local
area distributed systems and on local file systems.  For example, replaying
traces of real users searching on the WWW shows that sets can reduce latency
by over an order of magnitude across a range of factors.

@blankspace(2line)
@begin(transparent,size=10)
@b(Keywords:@ )@c<Search, distributed systems, file systems, information
retrieval, prefetching, performance. latency, modeling, dynamic sets, world
wide web>
@end(transparent)
@blankspace(1line)
@end(text)
@flushright(@b[(243 pages)])