Carnegie Mellon University Ph.D Dissertation CMU-CS-97-181: October 1997
Andrew Tomkins
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
This thesis has two parts, the first more practical, and the second more theoretical. The first part considers informed prefetching and caching in which an application provides information about its upcoming I/O accesses to the operating system, allowing the system to prefetch data and to make informed cache replacement decisions. I compare existing algorithms for this problem using trace-driven simulation, and use the results to develop a new algorithm that performs better than previous approaches, again under trace-driven simulation.
The second part considers weighted caching, a theoretical problem from the domain of on-line algorithms. I present an algorithm with competitive ratio O(log2 k) on (k + 1)-point spaces, the first poly-logarithmic ratio for this problem. I also give an almost-tight lower bound of W(log k) for any weighted caching problem on at least k + 1 points. I then show a connection between this problem and a new on-line k-server model in which the servers may rearrange themselves without cost during "free-time" between requests, and describe a series of results in the free-time model.
FULL THESIS: pdf / postscript