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

Title:

Bandwidth Constrained Placement in a WAN [ps, pdf]
Arun Venkataramani, Phoebe Wiedmann, and Mike Dahlin

Speaker: Carl Livadas

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.