The effect of time delays in the stability of load balancing algorithms for parallel computations

Authors

Chaouki T. Abdallah
J. D. Birdwell
John Chiasson
Zhong Tang
Nivedita Alluri
Tsewei Wang

Document Type

Article

Publication Date

12-9-2003

Abstract

Deterministic dynamic nonlinear time-delay systems are developed to model load balancing in a cluster of computer nodes used for parallel computations. The model is shown to be self consistent in that the queue lengths cannot go negative and the total number of tasks in all the queues are conserved (i.e., load balancing can neither create nor lose tasks). Further, it is shown that using the proposed load balancing algorithms, the system is stable. Experimental results are presented and compared with the predicted results from the analytical model. In particular, simulations of the models are compared with an experimental implementation of the load balancing algorithm on a parallel computer network.

Publisher

IEEE

Publication Title

Proceedings of the 42nd IEEE Conference on Decision and Control

ISSN

0191-2216

First Page

582

Last Page

587

DOI

10.1109/CDC.2003.1272626

Language (ISO)

English

Sponsorship

IEEE

Keywords

Analytical models, Clustering algorithms, Computational modeling, Load balancing, Computer Networks, Time Delay Systems

Recommended Citation

Abdallah, Chaouki T.; J. D. Birdwell; John Chiasson; Zhong Tang; Nivedita Alluri; and Tsewei Wang. "The effect of time delays in the stability of load balancing algorithms for parallel computations." Proceedings of the 42nd IEEE Conference on Decision and Control (2003): 582-587. doi:10.1109/CDC.2003.1272626.