-----------------------------------------------------------------------
TDS Seminar TDS Seminar TDS Seminar TDS Seminar TDS Seminar
-----------------------------------------------------------------------

Speaker: Carl Livadas
Place:   NE43-308
Time:    1-2:30pm
Date:    Sept. 21, 2001

The TDS seminar will involve the presentation of the following paper that
appeared in PODC 2001.

Title:	 Bandwidth Constrained Placement in a WAN

Abstract:

In this paper, we examine the bandwidth-constrained placement problem,
focusing on trade-offs appropriate for wide area network (WAN)
environments.  The goal is to place copies of objects at a collection of
distributed caches to minimize expected access times from distributed
clients to those objects subject to a maximum bandwidth constraint at each
cache.  We develop a simple algorithm to generate a bandwidth-constrained
placement by hierarchically refining an initial per-cache greedy placement.
We prove that this hierarchical algorithm generated a placement whose
expected access time is within a constant factor of the optimal placement's
expected access time.  We then proceed to extend this algorithm to compute
close to optimal placement strategies for dynamic environments.

-----------------------------------------------------------------------