David A. Bader
IEEE Fellow
AAAS Fellow
Professor
College of Computing
Georgia Tech
Atlanta, GA 30332


 
 

 

Dynamic Load Balancing in Distributed Systems in the Presence of Delays: A Regeneration-Theory Approach

A regeneration-theory approach is undertaken to analytically characterize the average overall completion time in a distributed system. The approach considers the heterogeneity in the processing rates of the nodes as well as the randomness in the delays imposed by the communication medium. The optimal one-shot load balancing policy is developed and subsequently extended to develop an autonomous and distributed load-balancing policy that can dynamically reallocate incoming external loads at each node. This adaptive and dynamic load balancing policy is implemented and evaluated in a two-node distributed system. The performance of the proposed dynamic load-balancing policy is compared to that of static policies as well as existing dynamic load-balancing policies by considering the average completion time per task and the system processing rate in the presence of random arrivals of the external loads.

Publication History

Versions of this paper appeared as:
  1. S. Dhakal, M.M. Hayat, J.E. Pezoa, C. Yang, and D.A. Bader, ``Dynamic Load Balancing in Distributed Systems in the Presence of Delays: A Regeneration-Theory Approach,'' IEEE Transactions on Parallel & Distributed Systems, 18(4):485-497, 2007.

Download this report in Adobe PDF


 
 

Last updated: February 26, 2007

 




Computational Biology



Parallel Computing



Combinatorics