  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.
