A Swarm Intelligence based Task Allocation Algorithm (SITA) for the Computational Grid

Abstract — This paper proposes the use of a Swarm Intelligence based approach (SITA) for Task Allocation and scheduling in a dynamically reconfigurable environment such as the computational Grid. SITA is a massively distributed task allocation algorithm that draws inspiration from the hugely efficient foraging and food hunting paradigm of ants. We employ the ant colony optimization (ACO), a population based search technique for the solution of combinatorial optimization problems for resource discovery in the Grid. Making use of evaporating pheromone trails, the algorithm adapts effortlessly to transient network conditions like congestion, node failure, link failure etc. The use of the distributed agents (ants) working in parallel and independent of each other for resource discovery obviates the need to maintain global state across all nodes. This leads to substantial savings in memory requirements. For our analysis we considered a constraint satisfaction scenario where the objective is to optimize the often conflicting parameters of cost and time where cost is the cost of utilizing a particular Grid resource and time is the time spent in task allocation. A detailed performance analysis is also presented where we analyze the effect of various parameter settings on SITA to better understand the factors on which good allocation depends