So-Grid is a set of bio-inspired algorithms tailored to the decentralized construction of a Grid information system that features adaptive and self-organization characteristics. Such algorithms exploit the properties of swarm systems, in which a number of entities/agents perform simple operations at the local level, but together engender an advanced form of swarm intelligence at the global level.

So-Grid provides two main functionalities: logical reorganization of resources, inspired by the behavior of some species of ants and termites that move and collect items within their environment, and resource discovery, inspired by the mechanisms through which ants searching for food sources are able to follow the pheromone traces left by other ants. These functionalities are correlated, since an intelligent dissemination can facilitate discovery.
In the Grid environment, a number of ant-like agents autonomously travel the Grid through P2P interconnections and use biased probability functions to:
(i) replicate resource descriptors in order to favor resource discovery;
(ii) collect resource descriptors with similar characteristics in nearby Grid hosts;
(iii) foster the dissemination of descriptors corresponding to fresh (recently updated) resources and to resources having high quality of service (QoS) characteristics.
Simulation analysis shows that the So-Grid replication algorithm is capable of reducing the entropy of the system and efficiently disseminating content. Moreover, as descriptors are progressively reorganized and replicated, the So-Grid discovery algorithm allows users to reach Grid hosts that store information about a larger number of useful resources in a shorter amount of time. The proposed approach features characteristics, including self-organization, scalability and adaptivity, which make it useful for a dynamic and partially unreliable distributed system.

A graphical description of the behavior of the replication algorithm is given in the following figure. For the sake of clarity, here the number of classes is set to 3, peers are connected in a bidimensional mesh instead of a scale-free topology, and only a portion of the Grid is shown, though the simulation was performed on a network with 2500 hosts. Different symbols and colors are associated with the three classes. Each peer is marked with the symbol and color that corresponds to the class to which the largest number of descriptors, stored by this peer, belong. Furthermore, the symbol size is proportional to the number of descriptors of the dominant class. For example, if circles correspond to class C1, a peer marked with a big circle stores many descriptors of this class, while a peer marked with a smaller circle stores fewer descriptors of the same class. In both cases, the descriptors of class C1 are the most numerous in this peer. The peers with a thicker border are representative peers, which work as attractors for query messages issued to discover resources of the dominant class. Two snapshots of the network are shown: the first is taken when the replication process is initiated (time 0), while the second is taken 400000 seconds later, in a quite steady situation. This figure shows that descriptors are initially distributed in a completely random fashion, but subsequently they are accumulated and reorganized by replication agents in separate regions of the Grid, according to their class.

A high-level description of the replication algorithm, performed by replication agents, is given in the flowchart reported in the following. Periodically, each agent performs a small number of P2P hops among Grid hosts. Whenever an agent arrives at a new Grid host, for every resource class, it evaluates the pick or drop probability function, specifically:
(i) if the agent does not carry any descriptor of this class, it evaluates the pick probability function, so as to decide whether or not to pick the descriptors of this class from the current host;
(ii) if the agent already carries some descriptors of this class, it evaluates the drop probability function, so as to decide whether or not to leave these descriptors in the current host. After picking the descriptors of a class, the agent will carry them until it drops them into another host, and then will try to pick other descriptors from another host.

So-Grid algorithms boast profitable characteristics such as: self-organization, since system entities are autonomous, and there is no central control; adaptive behavior, which allows a prompt reaction to the modifications of a dynamic environment; scalability, since the So-Grid algorithms are not biased by the Grid size. These characteristics derive from the operations of very simple agents, whose behavior is inspired by biological systems, in particular ant and termite colonies. Two different kinds of agents operate continuously and concurrently: some replicate and reorganize resource descriptors on the Grid, while the others perform resource discovery operations on behalf of users. Simulation showed that the So-Grid replication algorithm is effective in the controlled propagation and reorganization of information. This permits the definition of a semi-informed discovery algorithm that is able to find useful resources in a short time. The discovery algorithm drives message queries to Grid representative peers, which are elected within Grid regions that store a large number of resource descriptors having specific characteristics. An enhanced version of the replication algorithm is defined to foster the dissemination, and facilitate the discovery, of recently updated information and of high quality resources, in the case where there is a common agreement about the evaluation of resource quality. The So-Grid algorithms can be used in any Grid network in which (i) connections among hosts are deployed with a P2P overlay and (ii) users, to build their distributed applications, need to discover hardware and software resources belonging to given categories, so that they can choose those that are the most appropriate for their requirements. Moreover, the Web Services approach, which is adopted in modern Grid frameworks, like the Globus Toolkit, is particularly suitable to support the multiagent approach of So-Grid. Indeed, agent movements across the Grid can be handled as invocations among Web Services that are exposed by Grid hosts.

References

A. Forestiero, C. Mastroianni, and G. Spezzano. So-Grid: A self-organizing Grid featuring bio-inspired algorithms.
ACM Transactions on Autonomous and Adaptive Systems 3, 2, Article 5 (May 2008), 37 pages.

A. Forestiero, C. Mastroianni, G. Spezzano, "QoS-based Dissemination of Content in Grids".
Future Generation Computer Systems, vol. 24(3), Elsevier Science, March 2008.