  We consider the problem of fair resource allocation in a system where user
demands are dynamic, that is, where user demands vary over time. Our key
observation is that the classical max-min fairness algorithm for resource
allocation provides many desirable properties (e.g., Pareto efficiency,
strategy-proofness, and fairness), but only under the strong assumption of user
demands being static over time. For the realistic case of dynamic user demands,
the max-min fairness algorithm loses one or more of these properties.
  We present Karma, a new resource allocation mechanism for dynamic user
demands. The key technical contribution in Karma is a credit-based resource
allocation algorithm: in each quantum, users donate their unused resources and
are assigned credits when other users borrow these resources; Karma carefully
orchestrates the exchange of credits across users (based on their instantaneous
demands, donated resources and borrowed resources), and performs prioritized
resource allocation based on users' credits. We theoretically establish Karma
guarantees related to Pareto efficiency, strategy-proofness, and fairness for
dynamic user demands. Empirical evaluations over production workloads show that
these properties translate well into practice: Karma is able to reduce
disparity in performance across users to a bare minimum while maintaining
Pareto-optimal system-wide performance.
