AntCO²
Thesis work
Purpose
AntCO² is a Java library whose goal is to provide distribution advices to a distributed application (for example for very large simulations run on a grid).
To achieve this, AntCO² represents the application as a graph. The distributed entities of the application (processes, distributed objects, active objects, agents, etc.) are seen as nodes of the graph. Each time an entity communicates in a way or another with another entity, an edge is created in the graph. It is possible to that entities appear or disappear. In fact, the main goal of AntCO² is to manage such dynamic distributed applications.
The idea is to put highly communicating entities together on the same computing resource, as well as to balance the load between all available computing resources. These two criteria being in conflict, a trade-off must be achieved. This makes sense, since we want to minimise communications time between distributed entities to avoid latencies due to the network, and want to distribute the load on all the available computing resources according to their computing power.
We see highly communicating entities as ``organisations'' or communities that form, evolve and eventually disappear during the application lifetime. Such organisations correspond to the usual definition of communities in graphs, that is, set of nodes more interconnected one with another than with the rest of the graph.
Therefore, AntCO² is mainly based on a community or organisation detection method. We prefer the term ``organisation'' to the term ``communities'' since it carries the idea of a dynamic process.
The provided library is a prototype that only works on one machine. It is used to test the feasibility of the technique and can run on real applications as well as on test applications represented by dynamic graphs. It could yet be used as a centralised service to distribute applications, but it should be possible, in the future to distribute AntCO² with the distributed application it serve.
Method
The AntCO² algorithm uses collective intelligence mechanisms to assign computing resources to the distributed entities of the application. As this application is represented by a dynamic graph where nodes represent the entities, we associate with each computing resource a color and try color each node of the graph.
The algorithm is based on artificial ant colonies that travel through the graph. Each ant colony is associated with a color (and therefore a computing resource). Inside a colony, the ants collaborate to conquer parts of the graph. Their behavior is made to favor highly communicating groups of entities as territories. When a node pertains to a given colony it is colored by the color of the colony. We therefore say that the node should be placed on the corresponding computing resource. As ants inside a colony tend to collaborate to colonise the nodes that are highly communicating, these nodes tend to be colored with the same color.
Between colonies, at the contrary, ants compete. Each colony repulse the others. The global idea is that load balancing is achieved by the constant struggle of colonies to keep their territories.
These two conflicting behaviors (collaboration inside colonies and competition between colonies) correspond to the two conflicting goals : to ensure communicating entities of the application are on the same computing resource, while the computing load is balanced.
The ants colonise their environment using pheromone messages dropped in their environment, that is the graph representing the distributed application. Each colony owns a distinct pheromone. As each colony is mapped to a color, we say the pheromones are colored.
Using the pheromone levels we can decide which area of the graph is colonised by an ant colony.
Ants constantly maintain the pheromone on the graph, as it evaporates. This is the mechanism that allows to adapt to changes in the application. Each addition, evolution or removal of a distributed entity or communication between entities is reflected in the graph by the addition, evolution or removal of the corresponding node or edge, making the graph dynamic. Therefore the territories colonised by ants may appear, evolve and disappear.
As pheromones evaporate, if a previously colonised area of the graph is abandoned by a colony, it can be recolonised by another.
An example on the ``dolphins'' graph (courtesy of J. Newman) with two computing resources identified by the red and green colors. The large translucent circles on the edges represent pheromone levels of the dominant colony.
Usage
AntCO² works as a service. You provide events as input (an entity appear, evolve or disappear, a communication between entities appear, evolve and disappear, a computing resource appear, etc.), and regularly, AntCO² yield placement advices. The placement is done by assigning identifiers to each entity of the application. These identifiers correspond to each available computing resource. We usually talk of identifiers as ``colors'' and we say the graph corresponding to the distributed application is colored (however this does not correspond to a graph coloring problem as usually understood).
Download
You can fetch the library here.
Bibliography
- Competing Ants for Organization Detection: application to Dynamic Distribution
- , in Emergent Properties in Natural and Artificial Dynamical Systems, ed. Moulay Aziz Alaoui, Cyrille Bertelle, Springer Verlag, pp. 25-52, 2006, download, BibTeX, abstract
- Colored ants for distributed simulations
- , in ANTS, Brussels (Belgium), pp. 326-333, 2004, download, BibTeX, abstract
CSS