| First and Second Order Diffusive Methods for Rapid, Coarse, Distributed Load Balancing (Extended Abstract) (1998) | |||||||||||||||
Abstract | |||||||||||||||
| ) Bhaskar Ghosh S. Muthukrishnan y Martin H. Schultz z Informix Software Inc. U. Warwick Yale U. Abstract 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 0 on the nodes, determine a schedule to move weights in each step across edges 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 the tth step and M is a doubly stochastic matrix. We call these the first order schedules. First order schedules, although widely used in practice, have a serious drawback that they are very 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 = fiMw t +(1 \Gamma fi)w t\Gamma1 for some a... | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||