Design and Analysis of the M2LL Policy Distributed Algorithm for Load Balancing in Dynamic Networks
作者： Jacques M. Bahi , Raphaël Couturier , Abderrahmane Sider
DOI: 10.1007/11942634_21
关键词:
摘要: Load balancing a distributed/parallel system consists in allocating work (load) to its processors so that they all have process approximately the same amount of or amounts relation with their computation power. In this paper, we present new distributed algorithm implements M2LL policy (Most Least Loaded). aims indicate pairs processors, will exchange load, taking into account actually broken edges as well current load distribution system. The fixes neighboring by selecting priority most loaded and least each neighborhood. Our main result is implementation terminates after at (n/2).dt iterations where n dt are respectively number nodes degree time t.
springer.com
acm.org 
sci-hub.st 参考文章(18)
Marc Willebeek-LeMair, Anthony P. Reeves, Local v Global Strategies for Dynamic Load Balancing. international conference on parallel processing. pp. 569- 570 ,(1990)
Jacques M. Bahi, Jaafar Gaber, Load Balancing on Networks with Dynamically Changing Topology european conference on parallel processing. pp. 175- 182 ,(2001) , 10.1007/3-540-44681-8_27
Jacques Bahi, Raphaël Couturier, Flavien Vernier, Accelerated Diffusion Algorithms on General Dynamic Networks international conference on parallel processing. ,vol. 3019, pp. 77- 82 ,(2003) , 10.1007/978-3-540-24669-5_10
Ralf Diekmann, Andreas Frommer, Burkhard Monien, Efficient schemes for nearest neighbor load balancing parallel computing. ,vol. 25, pp. 789- 812 ,(1999) , 10.1016/S0167-8191(99)00018-6
Tiberiu Rotaru, Hans-Heinrich Nägeli, Dynamic load balancing by diffusion in heterogeneous systems Journal of Parallel and Distributed Computing. ,vol. 64, pp. 481- 497 ,(2004) , 10.1016/J.JPDC.2004.02.001
Robert Elsässer, Burkhard Monien, Robert Preis, Diffusion Schemes for Load Balancing on Heterogeneous Networks Theory of Computing Systems \/ Mathematical Systems Theory. ,vol. 35, pp. 305- 320 ,(2002) , 10.1007/S00224-002-1056-4
William Aiello, Baruch Awerbuch, Bruce Maggs, Satish Rao, Approximate load balancing on dynamic and asynchronous networks Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93. pp. 632- 641 ,(1993) , 10.1145/167088.167250
JACQUES M. BAHI, RAPHAËL COUTURIER, PHILIPPE VUILLEMIN, SOLVING NONLINEAR WAVE EQUATIONS IN THE GRID COMPUTING ENVIRONMENT: AN EXPERIMENTAL STUDY Journal of Computational Acoustics. ,vol. 14, pp. 113- 130 ,(2006) , 10.1142/S0218396X06002949
S.H. Hosseini, B. Litow, M. Malkawi, J. McPherson, K. Vairavan, Analysis of a graph coloring based distributed load balancing algorithm Journal of Parallel and Distributed Computing. ,vol. 10, pp. 160- 166 ,(1990) , 10.1016/0743-7315(90)90025-K
V. Kumar, A.Y. Grama, N.R. Vempaty, Scalable Load Balancing Techniques for Parallel Computers Journal of Parallel and Distributed Computing. ,vol. 22, pp. 60- 79 ,(1994) , 10.1006/JPDC.1994.1070