Affiliations: [a] SIMULA Research Laboratory, P.O.Box 134, 1325 Lysaker, Norway. E-mail: sharath@simula.no | [b] SINTEF ICT, P.O.Box 124, 0314 Oslo, Norway. E-mail: Geir.Horn@sintef.no | [x] Department of Computer Science, The University of York, York YO10 5DD, UK | [y] Department of Information Technology, National University of Ireland, Galway, Ireland
Abstract: Achieving acceptable application performance in a grid environment remains a difficult challenge. In particular, this is true for applications composed of services that require certain criteria regarding quality to be fulfilled in order to satisfy users' needs. The problem considered here is the partitioning of application services onto the available execution nodes of a grid environment in such a way that they satisfy certain minimum criteria regarding quality. Fundamentally, this is an NP-hard problem. We propose three algorithms based on the concepts of learning automata and the metaphor of foraging ants. The algorithms naturally follow a decentralised multi-agent method for solving the service partitioning problem. Moreover, they establish a distributed problem-solving mechanism that does not require the use of a central controller. The proposed algorithms have been rigorously tested and evaluated through extensive simulations on randomly generated application services and grid environments. The results indicate that learning is an essential component for achieving scalability and efficiency in nature-inspired systems.
Keywords: Service configuration, scheduling, mapping, partitioning, ant system
