Karma: Resource Allocation for Dynamic Demands

Abstract

Classical max-min fairness provides Pareto efficiency, strategy-proofness, and fairness when user demands are static, but loses one or more of these properties when demands vary over time. Karma is a resource-allocation mechanism for dynamic demands built around a credit system: users earn credits when others borrow their unused resources, and allocations are prioritized according to credit balances. The paper establishes guarantees for Pareto efficiency, strategy-proofness, and fairness, and evaluations on production workloads show that Karma minimizes performance disparity while maintaining Pareto-optimal system-wide performance.

BibTeX

@inproceedings{karma,
  author = {Vuppalapati, Midhul and Fikioris, Giannis and Agarwal, Rachit and Cidon, Asaf and Khandelwal, Anurag and {\'E}va Tardos},
  title = {{Karma: Resource Allocation for Dynamic Demands}},
  booktitle = {USENIX OSDI},
  year = {2023},
  month = jul
}