Placement algorithms for hierarchical cooperative caching and other location problems

In a large-scale information system, such as a digital library or the world wide web, a set of distributed caches can improve their effectiveness by cooperating with one another, both in serving each other's requests as well as in deciding what to store. This dissertation explores the potential of such cooperative caching, and provides basic placement algorithms using which the caches can coordinate their storage decisions.; The first part of the dissertation focuses on variants of the placement problem involving a single object. The most well-known of these variants are the facility location problems, which have received considerable attention in the operations research literature due to their widespread applicability. We prove that a simple local search heuristic, proposed about 25 years ago, yields polynomial-time constant-factor approximations for several metric facility location problems.; The second part of the dissertation addresses the simultaneous placement of a collection of objects in hierarchical networks. We provide both exact and approximate polynomial-time algorithms for this hierarchical placement problem. Our exact algorithm is based on a reduction to min-cost flow, and does not appear to be practical for large problem sizes. Hence we are motivated to look for simpler approximate algorithms. Our main result is a simple constant-factor approximation algorithm that admits an efficient distributed implementation.; The third and final part of the dissertation describes our simulation experiments which were performed to ascertain the practical potential of cooperative caching, and to investigate the practical performance of various placement and replacement algorithms. Driven by both synthetic and web-trace workloads, these experiments compare several traditional as well as novel caching algorithms. They demonstrate that cooperation improves performance significantly, especially when the cache sizes are small. More surprisingly, the experiments show that our amortizing algorithm yields placements that are extremely close, within 5%, to the optimal when the access patterns are stable. We also examine hybrid strategies to cope with changing access patterns.