FIRST-ORDER AND 2ND-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 connec ted graph G = (V, E) and a weight distribution w(0) on the nodes, dete rmine a schedule to move weights across edges in each step so as to (a pproximately) 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+l) = Mw(t) where w(t) is the weight distributio n 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 (1) = Mw(0); w(t+1) = beta Mw(t) + (1 - beta)w(t-1) for some appropria te beta; we call these the second-order schedules. In the idealized se tting of weights being real numbers, we adopt known results to show th at beta can be chosen so that the second-order schedule involves signi ficantly fewer steps than the first-order method for approximate load balancing. In the realistic setting when the weights are positive inte gers, we simulate the idealized schedules by maintaining I Owe You uni ts on the edges. Extensive experiments with simulated data and real-li fe data from JOSTLE, a mesh-partitioning software, show that the resul tant realistic schedule is close to the idealized schedule, and it aga in involves fewer steps than the first-order schedules for approximate load balancing. Our main result is therefore a fast algorithm for coa rse load balancing that can be used in a variety of applications.