Cooperative load balancing in distributed systems

• DOI: 10.1002/cpe.1331
• Publication Date: 2008-06-06T18:00:25Z
• Authors: D. Grosu; A. T. Chronopoulos; M. Y. Leung
• Keywords: FOS: Computer and information sciences; Computer Networks and Communications; FOS: Physical sciences; D.3.2; D.3.4; D.2.8; 02 engineering and technology; Astrophysics; Theoretical Computer Science; 0202 electrical engineering, electronic engineering, information engineering; D.3.4; D.3.2; Astrophysics (astro-ph); D.2.8; Computer Science Applications; Computational Theory and Mathematics; Computer Science - Distributed, Parallel, and Cluster Computing; Distributed, Parallel, and Cluster Computing (cs.DC); Software

AbstractA serious difficulty in concurrent programming of a distributed system is how to deal with scheduling and load balancing of such a system which may consist of heterogeneous computers. In this paper, we formulate the static load‐balancing problem in single class job distributed systems as a cooperative game among computers. The computers comprising the distributed system are modeled as M/M/1 queueing systems. It is shown that the Nash bargaining solution (NBS) provides an optimal solution (operation point) for the distributed system and it is also a fair solution. We propose a cooperative load‐balancing game and present the structure of NBS. For this game an algorithm for computing NBS is derived. We show that the fairness index is always equal to 1 using NBS, which means that the solution is fair to all jobs. Finally, the performance of our cooperative load‐balancing scheme is compared with that of other existing schemes. Copyright © 2008 John Wiley & Sons, Ltd.