Dynamic load balancing in distributed systems in the presence of delays: A regeneration-theory approach

Sagar Dhakal, Majeed M. Hayat, Jorge E. Pezoa, Cundong Yang, David A. Bader

Research output: Contribution to journalArticlepeer-review

81 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)485-497
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Volume18
Issue number4
DOIs
StatePublished - Apr 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Keywords

  • Distributed computing
  • Dynamic load balancing
  • Queuing theory
  • Renewal theory

Fingerprint

Dive into the research topics of 'Dynamic load balancing in distributed systems in the presence of delays: A regeneration-theory approach'. Together they form a unique fingerprint.

Cite this