CSR: Small: Designing Mechanisms for Resource Allocation in Competitive Real-Time Open Environments

诸如云计算、虚拟执行环境和网格计算等计算系统的最新趋势已经从集中式设计转向包括多个独立开发和操作的子系统的高度可扩展的、开放的和分布式系统。由于依赖于所有子系统所有者和开发人员真实地表达他们的资源需求，这种系统对需要实时保证的应用程序提出了基本的设计挑战。目前，没有任何实时开放系统环境框架阻止用户通过简单地歪曲其子系统的资源需求来获得系统资源的“不公平”分配。需要一种解决办法，正式保证在各子系统之间进行有效/公平的资源分配。本文所采用的方法是应用实时调度和博弈论(即算法机制设计)技术的新组合，为共享实时处理平台设计真值诱导分配机制。这些技术通过开发中间件实现和实时设置的网格仿真来验证和评估。在独立开发的子系统之间分配时间关键资源的可信方案是降低开发和运营成本、提高复杂计算系统可靠性的关键，而复杂计算系统是我们的社会和经济日益依赖的。除了技术的直接好处外，该项目还通过积极让本科生和代表性不足的学生参与研究，进一步促进了教育目标。

Recent trends in computing systems, such as cloud computing, virtual execution environments, and grid computing, have been away from centralized designs towards highly extensible, open, and distributed systems comprising multiple independently-developed and operated subsystems. Such systems present a fundamental design challenge for applications that require real-time guarantees, due to the reliance upon all subsystem owners and developers to truthfully express their resource requirements. Currently, no real-time open system environment framework prevents a user from obtaining an ``unfair'' allocation of system resources by simply misrepresenting their subsystem's resource requirements. A solution is needed, that formally guarantees an efficient/equitable resource allocation among subsystems. The approach taken here is to apply a novel combination of real-time scheduling and game theory (i.e., algorithmic mechanism design) techniques, to design truth-inducing allocation mechanisms for shared real-time processing platforms. These techniques are proven and evaluated by developing a middleware implementation and a grid simulation for a real-time setting.A trustworthy scheme for allocating time-critical resources among independently developed subsystems is a key to reducing development and operational costs, and increasing the reliability of the complex computing systems upon which our society and economy increasingly depend. Beyond direct benefits of the technology, this project furthers educational goals by actively involving undergraduate and underrepresented students in research.