  In the load balancing problem, each node in a network is assigned a load, and
the goal is to equally distribute the loads among the nodes, by preforming
local load exchanges. While load balancing was extensively studied in static
networks, only recently a load balancing algorithm for dynamic networks with a
bounded convergence time was presented. In this paper, we further study the
time complexity of load balancing in the context of dynamic networks.
  First, we show that randomness is not necessary, and present a deterministic
algorithm which slightly improves the running time of the previous algorithm,
at the price of not being matching-based. Then, we consider integral loads,
i.e., loads that cannot be split indefinitely, and prove that no matching-based
algorithm can have a bounded convergence time for this case.
  To circumvent both this impossibility result, and a known one for the
non-integral case, we apply the method of smoothed analysis, where random
perturbations are made over the worst-case choices of network topologies. We
show both impossibility results do not hold under this kind of analysis,
suggesting that load-balancing in real world systems might be faster than the
lower bounds suggest.
