AF: Small: Algorithmic and Market Design Challenges in Cloud Computing

The global market for cloud computing is worth hundreds of billions of dollars, consumes about one percent of worldwide electricity use, and is growing rapidly. Thus, even small improvements in its operation would have substantial impacts on economic activity and society's ability to meet sustainability goals. Despite their importance, cloud-computing resources are currently priced and allocated using simple approaches.

On the pricing side, most resources are sold using utility-style pricing where resources whose usage can be measured are priced based on the time they are used for and quantity used. On the allocation side simple policies are used to assign resources to customers and manage contention. This project will develop new algorithms and market designs to enable fairer and more efficient solutions to resource allocation problems faced by cloud providers around two main themes: (1) managing future demand and (2) simultaneous allocation of multiple resources.

While the focus of the project is on challenges arising from cloud computing, similar challenges arise in other contexts, for example in electricity markets adapting to increased use of renewable resources with high variability in supply.

With utility-style pricing, cloud providers have no information about the future plans of their customers, resulting in challenging online problems when managing future demand. This project will develop new resource-allocation algorithms to manage highly stochastic demands in the online setting as well as analyze new market designs that pair richer information elicited from customers about their future needs with novel algorithms to make use of that information.

What makes this problem particularly complex is that satisfying these demands requires simultaneous allocation of multiple resources. Fair and efficient division of multiple resources with Leontief utilities (which require resources to be perfectly matched in quantity, like hot dogs and buns) has been studied for a decade since the introduction of the dominant resource-fairness algorithm, which attempts to equalize the amount each customer receives of their most demanded resource and was explicitly inspired by the challenges of allocating cloud-computing resources.

However, several important issues have received only limited attention, thereby limiting the opportunities to apply these techniques in cloud systems. This project is addressing two such issues. First, many customers are seeking to complete a fixed amount of work, and so care about the time taken to complete that work rather than directly about the immediate quantity of resources allocated.

Second, this is not a static allocation problem to be solved but a dynamic, online one. Thus, this project is developing new analyses and variants of fair-division approaches such as dominant resource fairness and maximum Nash welfare (the product of customer values) suitable for settings with limited demands and dynamic allocations.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.