Toward Self-Tuning Algorithms for Distributed Resource Allocation

点击翻译按钮获取中文摘要

Intellectual merit. Numerous basic questions related to resource allocation remain open. This projectaddresses some of the central open questions in the area. Is it possible to build a resource allocationinfrastructure 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 drawingon established techniques from a wide range of areas of computer science including online algorithms andcompetitive analysis, parallel and distributed computation, and randomized algorithms and probabilisticanalysis 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 yieldan 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 modularsolution 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.