Toward Self-Tuning Algorithms for Distributed Resource Allocation

智力上的优点。与资源分配有关的许多基本问题仍然悬而未决。这个项目解决了该地区的一些中心公开问题。有可能建立一个既通用又高效的资源配置基础设施吗？构建有效的资源分配算法的合适基元是什么？这些原语能否以完全分布式的方式高效实现？有没有可能对互联网进行协调，以便以一个公平的价格，任意的用户可以轻松地利用其未得到充分利用的巨大资源池？该项目通过利用计算机科学广泛领域的成熟技术来解决这些问题，这些领域包括在线算法和竞争分析、并行和分布式计算、随机化算法和概率分析，以及计算机科学之外的各个领域，如博弈论、运筹学和经济学。关于文本压缩，提出的算法框架可能会在运行时间和压缩比之间产生一个有趣的新折衷，以解决这个基本问题。随着分布式系统规模和复杂性的不断增加，资源分配问题需要一种模块化的解决方案。通用的自调整资源分配基础设施提供了这样一个模块，也为互联网资源交换提供了理想的平台。这样一个交易所的建立将使一个广泛的新的应用类别成为可能。例如，它将允许任意程序在短时间内廉价地获取大量CPU资源，以便快速执行计算密集型但高度并行化的任务。通过探索资源配置的基本权衡，理论计算机科学已经在重塑互联网基础设施方面发挥了重要作用。如果以最近的历史为鉴，这个项目所涉及的资源分配问题的进展将对互联网的性质产生深远的影响。此外，本项目中探索的文本压缩框架有可能提高某些新兴应用程序的性能，例如互联网搜索，在这些应用程序中，在压缩文件中高效搜索字符串的能力代表着明显的优势。

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.