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

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

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.