Multi-Resource Fair Allocation with Bounded Number of Tasks in Cloud Computing Systems

Provided by: Yunjie Shi
Topic: Cloud
Format: PDF
The authors study a problem of multi-resource fair allocation with bounded number of tasks, and propose the Lexicographically Max-Min Dominant Share (LMMDS) fair al-location mechanism, which is a generalization of the popular Dominant Resource Fairness (DRF) mechanism. They prove that LMMDS satisfies sharing incentives, group strategy-proofness, envy-freeness, and Pareto efficiency, by exploiting the properties of the optimal solution. In addition, they design a non-trivial optimal algorithm to find a LMMDS fair al-location whose running time is linear in the number of users' n, when the number of types of resources m is bounded. Finally, they prove that the approximation ratio of LMMDS (or DRF) is infinity for the general case, and exactly n for a special case, improving the previous best lower bound m.

Find By Topic