Discrete Load Balancing is (almost) as Easy as Continuous Load Balancing

摘要

We consider the problem of diffusion-based load balancing on a distributed network with n processors. If the load is arbitrarily divisible, then the convergence is fairly well captured in terms of the second largest eigenvalue of the diffusion matrix. As for many applications load can not be arbitrarily divided, we consider a model where load consists of indivisible, unit-size tokens. Quantifying by how much this integrality assumption worsens the efficiency of load balancing algorithms is a natural question which has been posed by many authors [9, 15, 16, 19, 6, 17]. In this paper we show essentially that discrete load balancing is almost as easy as continuous load balancing. More precisely, we present a fully distributed, randomized algorithm for discrete load balancing that balances the load up to an additive constant error on any graph in time O(log(Kn)/(l-λ_2)), where K is the initial imbalance and λ_2 is the second largest eigenvalue of the diffusion matrix. This improves and tightens a result of Elsasser, Monien, Scharnberger (2006) who proved a runtime bound of O((og(K) + (logn)~2)/(l -A2)). We also develop a load balancing algorithm based on routing that achieves a runtime of O(D . logn), where D is the diameter of the graph.