Tight Worst-Case Completion-Time Bounds for Dominant Resource Fairness
Mugen Blue, Sungjin Im, Alexander Lindermayr
原文摘要
Dominant Resource Fairness (DRF) is an influential policy for sharing multiple resources among jobs with heterogeneous demands. It combines sharing incentive, strategy-proofness, envy-freeness, and Pareto efficiency, making it particularly attractive for shared computing systems. DRF has been implemented in major resource-management frameworks, including Apache Mesos and Hadoop YARN. DRF is also nonclairvoyant: it requires no advance knowledge of job sizes, making it practical when processing requirements are difficult to predict. This motivates understanding its completion-time performance relative to an optimal schedule that knows all job sizes. However, elementary arguments can only give an $Ω(\sqrt D)$ lower bound and an $O(D)$ upper bound for total completion time, where $D$ is the number of resource types. In this paper, we close this gap by proving that DRF is $Θ(\sqrt D)$-competitive. More generally, for every fixed real $q\geq1$, we show that DRF is $Θ(D^{1/(q+1)})$-competitive for the $\ell_q$ norm of completion times, with larger $q$ placing greater emphasis on late-finishing jobs. These bounds hold with arbitrary release times. We also give a refined analysis of total completion time for small $D$.
cs.DS