TITLE: Approximation Algorithms for Data Placement in Distributed Networks

SPEAKER: Rajmohan Rajaraman

WHERE: 149 Cullinane Hall

WHEN: 2PM, Friday, May 4, 2001

ABSTRACT:

Consider a network of nodes with individual storage capacities, in
which each node periodically issues a request for an object drawn from
an arbitrary collection of objects.  In this talk, we consider the
problem of placing copies of the objects among the nodes such that the
average access cost is minimized.

We will begin with a discussion on applications of the above placement
problem -- e.g., in digital libraries, content delivery networks, and
peer-to-peer networks -- and appropriate formulations of the problem.
We will discuss models for the network, the access patterns, node
capacity constraints, and the dynamics of the system.

After the initial discussion, the talk will briefly describe two
results that were obtained assuming that the following conditions are
satisfied: the frequency with which each node accesses each object is
known; each node has a cache of known capacity; any cache can be
accessed by any node; any request is satisfied by the closest node
with a copy of the desired object.  The first result is a simple
distributed constant-factor approximation algorithm for the placement
problem in the special case of hierarchical networks.  The second is a
centralized constant-factor approximation algorithm based on a
relaxation of the underlying linear program.

The model for the talk will the same as in the previous seminars:
interactive, a healthily skeptical audience (as Gene has been
emphasizing!), with the primary aim of identifying new research
problems.

(The results that will be discussed in this talk include joint work
with Ivan Baev, Madhukar Korupolu, and Greg Plaxton.)