  In this paper we study dynamic averaging load balancing on general graphs. We
consider infinite time and dynamic processes, where in every step new load
items are assigned to randomly chosen nodes. A matching is chosen, and the load
is averaged over the edges of that matching. We analyze the discrete case where
load items are indivisible, moreover our results also carry over to the
continuous case where load items can be split arbitrarily. For the choice of
the matchings we consider three different models, random matchings of linear
size, random matchings containing only single edges, and deterministic
sequences of matchings covering the whole graph. We bound the discrepancy,
which is defined as the difference between the maximum and the minimum load.
Our results cover a broad range of graph classes and, to the best of our
knowledge, our analysis is the first result for discrete and dynamic averaging
load balancing processes. As our main technical contribution we develop a drift
result that allows us to apply techniques based on the effective resistance in
an electrical network to the setting of dynamic load balancing.
