Design and Analysis of the M2LL Policy Distributed Algorithm for Load Balancing in Dynamic Networks

摘要

Load balancing a distributed/parallel system consists in allocating work (load) to its processors so that they all have to process approximately the same amount of work or amounts in relation with their computation power. In this paper, we present a new distributed algorithm that implements the M2LL policy (Most to Least Loaded). M2LL aims to indicate pairs of processors, that will exchange load, taking into account actually broken edges as well as the current load distribution in the system. The M2LL policy fixes the pairs of neighboring processors by selecting with priority the most loaded and the least loaded of each neighborhood. Our main result is that the M2LL distributed implementation terminates after at most (n/2).dt iterations where n and d_t are respectively the number of nodes and the degree of the system at time t.