Collectives for multiple resource job scheduling across heterogeneous servers

ABSTRACT

Efficient management of large-scale, distributed data storage and processing systems is a major challenge for many computational applications. Many of these systems are characterized by multi resource tasks processed across a heterogeneous network. Conventional approaches, such as load balancing, work well for centralized, single resource problems, but breakdown in the more general case. In addition, most approaches are often based on heuristics which do not directly attempt to optimize the world utility. In this paper, we propose an agent based control system using the theory of collectives. We configure the servers of our network with agents who make local job scheduling decisions. These decisions are based on local goals which are constructed to be aligned with the objective of optimizing the overall efficiency of the system. We demonstrate that agents configured using collectives outperform both team games and load balancing, by up to four times for the latter.

REFERENCES

• 1: William Leinberger , George Karypis , Vipin Kumar , Rupak Biswas, Load Balancing across Near-Homogeneous Multi-Resource Servers, Proceedings of the 9th Heterogeneous Computing Workshop, p.60, May 01-01, 2000
• 2: Behrooz A. Shirazi , Krishna M. Kavi , Ali R. Hurson, Scheduling and Load Balancing in Parallel and Distributed Systems, IEEE Computer Society Press, Los Alamitos, CA, 1995
• 3: Kagan Tumer , Adrian K. Agogino , David H. Wolpert, Learning sequences of actions in collectives of autonomous agents, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544832]
• 4: D. H. Wolpert and K. Tumer. Optimal payo functions for members of collectives. Advances in Complex Systems, 4(2/3):265--279, 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Design, Theory

Keywords:
collectives, computational grid, job scheduling, multi-resource optimization, reinforcement learning