Improving fair and truthful resource sharing in cloud computing
Strategyproof Multi-Resource Allocation in Cloud Computing via Adaptive-Speed Fairness
Computer Science and Game Theory
Summary
Cloud computers need to share many resources like CPU and memory fairly among users. A popular method called Dominant Resource Fairness keeps sharing honest and envy-free but can waste resources. The authors develop a new method, Adaptive-Speed Fairness, which improves efficiency while still being fair and strategy-proof. For two resources, this new method better balances fairness and overall performance, and for three or more resources, they prove strong limits on what is possible. They also test their approach using real and simulated data, showing it works well in practice.
What this means in practice
- •For cloud infrastructure teams: Allocate multiple resources efficiently and fairly among cloud users while ensuring users cannot gain by misreporting their needs.
- •For data center operators: Improve resource sharing policies to increase overall throughput and user satisfaction in multi-resource environments.
Authors
Yunpeng Lou, Junjie Luo
Abstract
We study fair and strategy-proof allocation of multiple divisible resources with Leontief utilities, motivated by cloud computing. The canonical mechanism, Dominant Resource Fairness (DRF), satisfies sharing incentive (SI), envy-freeness (EF), strategy-proofness (SP), and Pareto optimality (PO), but can be highly inefficient in terms of utilitarian social welfare. Under the classical approximation benchmark, no mechanism satisfying even one of SI, EF, and SP can improve on the trivial worst-case guarantee. We therefore adopt the recently introduced \emph{fair-ratio} benchmark, which compares a mechanism only with the welfare-maximizing allocation that itself satisfies SI and EF. For two resources, we introduce Adaptive-Speed Fairness (ASF), a unified parametric framework that captures previous mechanisms as special or boundary cases. Every ASF mechanism satisfies SI, EF, and PO, and we derive a general sufficient condition that guarantees SP. Optimizing within this framework yields a strategy-proof mechanism with asymptotic fair-ratio $2/(2\sqrt2-1)\approx1.09384$, substantially improving the previous best guarantee $3-\sqrt{3} \approx 1.268$. We complement this upper bound with a lower bound of $1.07894$ for all ASF mechanisms, showing that our best mechanism is close to optimal within this framework. Experiments on synthetic and Google trace-generated instances support the theory and demonstrate strong empirical performance. Finally, we establish a sharp dimensional boundary. For the general setting with $m\ge3$ resources, every mechanism satisfying SI and SP has fair-ratio exactly $m$. The same factor-$m$ lower bound continues to hold for randomized mechanisms satisfying ex-post SI and truthfulness in expectation.