Intellectual merit. Numerous basic questions related to resource allocation remain open. This project addresses some of the central open questions in the area. Is it possible to build a resource allocation infrastructure that is both general-purpose and efficient? What are the appropriate primitives from which to construct efficient resource allocation algorithms? Can these primitives be efficiently implemented in a fully distributed manner? Is it possible to coordinate the internet so that, for a fair price, an arbitrary user can easily tap into its vast pool of underutilized resources? The project addresses these questions by drawing on established techniques from a wide range of areas of computer science including online algorithms and competitive analysis, parallel and distributed computation, and randomized algorithms and probabilistic analysis as well as various fields outside of computer science, such as game theory, operations research, and economics. With regard to text compression, the proposed algorithmic framework appears likely to yield an interesting new tradeoff between running time and compression ratio for this fundamental problem. Broader impact. The ever-increasing size and complexity of distributed systems demands a modular solution to the resource allocation problem. A general-purpose self-tuning resource allocation infrastructure provides such a module, and also provides the ideal platform for an internet resource exchange. The establishment of such an exchange would enable a broad new class of applications. For example, it would allow an arbitrary program to cheaply acquire vast CPU resources for a brief period of time in order to rapidly perform a computationally intensive, but highly parallelizable, task. Through the exploration of fundamental tradeoffs in resource allocation, theoretical computer science has already played a major role in reshaping the infrastructure of the internet. If the recent past is any guide, progress on the resource allocation questions addressed in this project will have a profound impact on the nature of the internet. In addition, the framework for text compression explored in this project has the potential to boost performance in certain emerging applications, such as internet search, where the ability to efficiently search for a string in the compressed file represents a distinct advantage.
