Agent-based load balancing on homogeneous minigrids: Macroscopic modeling and characterization

Jiming LIU*, Xiaolong Jin, Yuanshi Wang

*Corresponding author for this work

Research output: Contribution to journalReview articlepeer-review

79 Citations (Scopus)

Abstract

In this paper, we present a macroscopic characterization of agent-based load balancing in homogeneous minigrid environments. The agent-based load balancing is regarded as agent distribution from a macroscopic point of view. We study two quantities on minigrids: the number and size of teams where agents (tasks) queue. In macroscopic modeling, the load balancing mechanism is characterized using differential equations. We show that the load balancing we concern always converges to a steady state. Furthermore, we show that load balancing with different initial distributions converges to the same steady state gradually. Also, we prove that the steady state becomes an even distribution if and only if agents have complete knowledge about agent teams on minigrids. Utility gains and efficiency are introduced to measure the quality of load balancing. Through numerical simulations, we discuss the utility gains and efficiency of load balancing in different cases and gives a series of analysis. In order to maximize the utility gain and the efficiency, we theoretically study the optimization of agents' strategies. Finally, in order to validate our proposed agent-based load balancing mechanism, we develop a computing platform, called Simulation System for Grid Task Distribution (SSGTD). Through experimentation, we note that our experimental results in general confirm our theoretical proofs and numerical simulation results from the proposed equation system. In addition, we final a very interesting phenomenon, that is, agent-based load balancing mechanism is topology-independent.

Original languageEnglish
Pages (from-to)586-598
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Volume16
Issue number7
DOIs
Publication statusPublished - Jul 2005

Scopus Subject Areas

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

User-Defined Keywords

  • Agents
  • Convergence
  • Grid simulation
  • Homogeneous minigrids
  • Load balancing
  • Macroscopic modeling
  • Steady states
  • Task distribution

Fingerprint

Dive into the research topics of 'Agent-based load balancing on homogeneous minigrids: Macroscopic modeling and characterization'. Together they form a unique fingerprint.

Cite this