Dynamic Weighted Fairness with Minimal Disruptions

Sungjin Im, Benjamin Moseley, Kamesh Munagala, Kirk Pruhs

Abstract

In this paper, we consider the following dynamic fair allocation problem: Given a sequence of job arrivals and departures, the goal is to maintain an approximately fair allocation of the resource against a target fair allocation policy, while minimizing the total number of disruptions, which is the number of times the allocation of any job is changed. We consider a rich class of fair allocation policies that significantly generalize those considered in previous work. We first consider the models where jobs only arrive, or jobs only depart. We present tight upper and lower bounds for the number of disruptions required to maintain a constant approximate fair allocation every time step. In particular, for the canonical case where jobs have weights and the resource allocation is proportional to the job's weight, we show that maintaining a constant approximate fair allocation requires $\Theta(\log^* n)$ disruptions per job, almost matching the bounds in prior work for the unit weight case. For the more general setting where the allocation policy only decreases the allocation to a job when new jobs arrive, we show that maintaining a constant approximate fair allocation requires $\Theta(\log n)$ disruptions per job. We then consider the model where jobs can both arrive and depart. We first show strong lower bounds on the number of disruptions required to maintain constant approximate fairness for arbitrary instances. In contrast we then show that there there is an algorithm that can maintain constant approximate fairness with $O(1)$ expected disruptions per job if the weights of the jobs are independent of the jobs arrival and departure order. We finally show how our results can be extended to the setting with multiple resources.

Introduction

In modern computer systems, such as large-scale data centers, resources like CPU, memory, and bandwidth must be distributed fairly among competing jobs. However, the set of active jobs is dynamic; new jobs arrive and existing ones finish. Maintaining perfect fairness in such a dynamic environment is challenging because every arrival or departure theoretically requires recalculating and reassigning resources for all active jobs. These reassignments, known as disruptions, incur significant overhead, including context switching and resource re-allocation costs.

While previous research addressed "uniform fairness" (where all jobs are treated equally), this work tackles the more complex "weighted fairness" problem. In this setting, jobs have different priorities or weights. The core objective is to find the optimal trade-off: how much fairness can be maintained while minimizing the total number of disruptions?

Methodology

The authors employ theoretical analysis to establish both upper and lower bounds for disruption costs across various fairness models. Their primary algorithmic innovation is a monotone transform strategy, which consists of three main components:

  1. Job Grouping: For weighted arrivals, jobs are partitioned into "buckets" based on exponentially increasing weights.
  2. Slowly Growing Functions: The algorithm maps ideal fair shares to a discrete set of values using a slowly growing function $g(x)$, often related to the iterated logarithm $\log^* n$. By only updating a job's allocation when its ideal share crosses these discrete thresholds, the number of disruptions is minimized while maintaining a constant-factor approximation of the ideal fair share.
  3. Randomized Thresholds: To handle the more difficult arrival-departure model, the authors propose a randomized algorithm that triggers re-allocations only when the total system weight crosses specific random thresholds.

Theoretical Insights

The study reveals several fundamental properties of dynamic fairness:

  • The Power of $\log^* n$: In the arrival-only model for weighted jobs, the required disruptions per job are $\Theta(\log^* n)$. Given that the iterated logarithm grows extremely slowly, this result suggests that near-perfect fairness is achievable with very few disruptions in practice.
  • The Difficulty of Departures: Weighted fairness becomes significantly more complex when jobs can both arrive and depart. The authors prove that any deterministic algorithm may face a polynomial number of disruptions in the worst case.
  • Randomization as a Solution: By assuming a "random permutation" model—where job weights are independent of their arrival and departure order—the authors demonstrate that the expected number of disruptions can be reduced to $O(1)$ per job.

Key Results

The paper establishes a comprehensive hierarchy of bounds for different fairness policies and resource dimensions. Notably, the techniques extend beyond single-resource models to multi-dimensional settings like Dominant Resource Fairness (DRF) and Cobb-Douglas utilities.

Summary of disruption bounds for various fairness models and arrival/departure scenarios.

As shown in the table above, the disruption complexity varies significantly based on the fairness model and the arrival/departure dynamics. For instance, while Weighted Round Robin in a single dimension requires only $\Theta(\log^* n)$ disruptions for arrivals, the introduction of departures leads to a polynomial lower bound of $\Omega(n^{1/(4c+1)})$.

Conclusion and Future Work

This work provides a rigorous foundation for understanding the stability of fair allocation policies. However, several avenues for future research remain:

  • Work-Conserving Models: The current analysis assumes job departure times are independent of their resource allocation. Future work could incorporate models where higher resource rates lead to earlier completion.
  • DRF Optimization: While the authors provide bounds for multi-dimensional fairness, they conjecture that specific policies like DRF might admit even tighter bounds than the general monotone case.
  • Offline Optimal Trade-offs: Determining the absolute minimum disruptions possible when the sequence of arrivals and departures is known in advance remains an open computational problem.

Summary updated

Abstract

In this paper, we consider the following dynamic fair allocation problem: Given a sequence of job arrivals and departures, the goal is to maintain an approximately fair allocation of the resource against a target fair allocation policy, while minimizing the total number of disruptions, which is the number of times the allocation of any job is changed. We consider a rich class of fair allocation policies that significantly generalize those considered in previous work. We first consider the models where jobs only arrive, or jobs only depart. We present tight upper and lower bounds for the number of disruptions required to maintain a constant approximate fair allocation every time step. In particular, for the canonical case where jobs have weights and the resource allocation is proportional to the job's weight, we show that maintaining a constant approximate fair allocation requires $\Theta(\log^* n)$ disruptions per job, almost matching the bounds in prior work for the unit weight case. For the more general setting where the allocation policy only decreases the allocation to a job when new jobs arrive, we show that maintaining a constant approximate fair allocation requires $\Theta(\log n)$ disruptions per job. We then consider the model where jobs can both arrive and depart. We first show strong lower bounds on the number of disruptions required to maintain constant approximate fairness for arbitrary instances. In contrast we then show that there there is an algorithm that can maintain constant approximate fairness with $O(1)$ expected disruptions per job if the weights of the jobs are independent of the jobs arrival and departure order. We finally show how our results can be extended to the setting with multiple resources.
BibTeX
@article{im2020dynamic,
  author = {Sungjin Im and Benjamin Moseley and Kamesh Munagala and Kirk Pruhs},
  title = {{Dynamic Weighted Fairness with Minimal Disruptions}},
  journal = {Proc. ACM Meas. Anal. Comput. Syst.},
  year = {2020},
  doi = {10.1145/3379485},
}
Figure