CAREER: Scheduling and Resource Allocation in the Cloud using Graphical Models and Randomized Algorithms

可伸缩性是云计算被广泛采用的关键。未能规模化导致社交网络巨头MySpace的灭亡，无法支持超过系统容量10%的用户负载，数据中心每年的电力支出高达45亿美元，以及云中缺乏任何复杂的测量和监控系统。云的大小通常由数万台机器组成，这迫使人们使用低复杂度的算法，而当系统变大时，这种算法在设计上很幼稚，会导致性能显著下降。现有的算法往往是为较小的内部系统设计精确的最优解，并且由于其集中式高复杂性的性质而不能扩展。该研究通过设计一套低复杂度的算法来克服现有工作的局限性，这些算法仅在系统规模增长到无穷大时才是精确最优的，但在有限和大型系统中非常接近最优。这些算法旨在应对云中动态扩展、多租户和数据密集型的挑战，以及搜索、社交网络和地图缩减等不同应用程序工作负载的挑战。这项研究借鉴并贡献了图形模型和随机化算法领域，这两个领域都在本地交换稀疏信息，以在大系统中实现复杂的全局目标。该项目还包括以讲习班和实验室开放参观等形式的重要外联方案，以促进本科生研究以及妇女和代表性不足的少数群体的参与。

Scalability is crucial for cloud computing to be widely adopted. Failure to scale has resulted in the demise of the social networking giant MySpace, the inability to support a user load greater than 10% of system capacity, a $4.5 billion annual power expenditure on data centers and a lack of any sophisticated measurement and monitoring systems in the cloud. The size of a cloud, which often consists of tens of thousands of machines, compels the use of low-complexity algorithms, which, when naively designed, cause significant performance degradation as the system grows large. Existing algorithms are often designed for exact, optimal solutions for smaller in-house systems and do not scale due to their centralized high-complexity nature.This research overcomes the limitation of existing work by designing a suite of low-complexity algorithms for web services, data management, and measurement and monitoring in the cloud, which are exactly optimal only as the system size grows to infinity, but very close to optimal in finite and large systems. The algorithms are designed to address the challenges with dynamic scaling, multi-tenancy and data-intensiveness in the cloud, and for different application workloads including search, social networks and map-reduce. The research draws upon and contributes to the fields of graphical models and randomized algorithms, both of which exchange sparse information locally to achieve complex global objectives in large systems. The project also includes significant outreach programs in the form of workshops and lab open-houses, to promote undergraduate research, and the participation of women and under-represented minorities.