First- and second-order diffusive methods for rapid, coarse, distributed load balancing

We consider the following general problem modeling load balancing in a variety of distributed settings. Given an arbitrary undirected connected graph G = (V, E) and a weight distribution w⁰ on the nodes, determine a schedule to move weights across edges in each step so as to (approximately) balance the weights on the nodes. We focus on diffusive schedules for this problem. All previously studied diffusive schedules can be modeled as w^t+1 = Mw^t where w^t is the weight distribution after t steps and M is a doubly stochastic matrix. We call these the first-order schedules. First-order schedules, although widely used in practice, are often slow. In this paper we introduce a new direction in diffusive schedules by considering schedules that are modeled as: w¹ = Mw⁰; w^t+1 = βMw^t + (1 - β)w^t-1 for some appropriate β; we call these the second-order schedules. In the idealized setting of weights being real numbers, we adopt known results to show that βcan be chosen so that the second-order schedule involves significantly fewer steps than the first-order method for approximate load balancing. In the realistic setting when the weights are positive integers, we simulate the idealized schedules by maintaining I Owe You units on the edges. Extensive experiments with simulated data and real-life data from JOSTLE, a mesh-partitioning software, show that the resultant realistic schedule is close to the idealized schedule, and it again involves fewer steps than the first-order schedules for approximate load balancing. Our main result is therefore a fast algorithm for coarse load balancing that can be used in a variety of applications.