Toward Self-Tuning Algorithms for Distributed Resource Allocation

分布式资源分配的自调整算法

• 批准号: 0635203
• 负责人: C. Greg Plaxton
• 金额: $ 25万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-02-01 至 2012-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0635203&HistoricalAwards=false
• 关键词: Toward; Self; Tuning; Algorithms; Distributed

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.

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