The Anthill Project

Recent peer-to-peer (P2P) systems are characterized by decentralized control, large scale and extreme dynamism of their operating environment.  As such, they can be seen as instances of complex adaptive systems (CAS) typically found in biological and social sciences.  Anthill is a framework to support the  design, implementation and evaluation of P2P applications based on ideas such as multi-agent and evolutionary programming borrowed from CAS. An Anthill system consists of a dynamic network of peer nodes; societies of adaptive agents travel through this network, interacting with nodes and cooperating with other agents in order to solve complex problems.  Anthill can be used to construct different classes of P2P services that exhibit resilience, adaptation and self-organization properties.

Peer-to-peer (P2P) systems are characterized by decentralized control, large scale and extreme dynamism of their operating environment. Developing applications that can cope with these characteristics requires a paradigm shift, placing adaptation, resilience and self-organization as primary concerns.  We believe that  complex adaptive systems (CAS), which have been used to explain certain biological, social and economical phenomena, can be the basis of a programming paradigm for P2P applications.

In order to pursue this idea, we are developing Anthill, a framework to support the design, implementation and evaluation of P2P applications based on ideas such as multi-agent systems (MAS) and evolutionary programming borrowed from CAS. A MAS is a collection of autonomous agents that can observe their environment and perform simple local computations leading to actions based on these observations. The behavior of an agent may be non-deterministic and its actions may modify the agent environment as well as the agent location within the environment. What distinguishes MAS from other agent models is that there is no central coordination of activity. MAS often exhibit a property called swarm intelligence whereby a collection of simple agents of very limited individual capabilities achieves "intelligent" collective behavior. In this manner, they are able to solve problems that are beyond the capabilities or knowledge of individual agents. In our opinion, MAS can be profitably adopted for the design of innovative peer-to-peer algorithms.

As an example of a distributed multi-agent system drawn from nature, consider an ant colony. Several species of ants are known to group objects in their environment (e.g., dead corpses) into piles so as to clean up their nests. Observing this behavior, one could be mislead into thinking that the cleanup operation is being coordinated by some "leader'' ants.  Resnick describes an artificial ant colony exhibiting this very same behavior in a simulated environment. Resnick's artificial ant follows three simple rules: (i) wander around randomly, until it encounters an object; (ii) if it was carrying an object, it drops the object and continues to wander randomly; (iii) if it was not carrying an object, it picks the object up and continues to wander. 

Despite their simplicity, a colony of these ``unintelligent'' ants is able to group objects into large clusters, independent of their initial distribution. This simple algorithm could be used to design distributed data analysis and search algorithms, by enabling artificial ants to travel through a network and cluster  "similar" information items. It is also possible to consider a simple variant (the inverse) of the above artificial ant that drops an object that it may be carrying only after having wandered about randomly  "for a while"' without encountering other objects.  Colonies of such ants try to disperse objects uniformly over their environment rather than clustering them into piles.  As such, they could form the basis for a distributed load balancing algorithm.

A Java prototype of the Anthill runtime environment has been developed, based on JXTA. an open-source P2P project promoted by Sun Microsystems. The benefits of basing our implementation on JXTA are several. For example, JXTA allows the use of different transport layers for communication, including TCP/IP and HTTP,  and deals with issues related to firewalls and NAT. In addition to the runtime environment, Anthill includes a simulation environment to help developers analyze and evaluate the behavior of their P2P systems. Simulating different P2P applications require developing  appropriate ant algorithms and a corresponding request generator characterizing user interactions with the application. Each simulation study is specified using XML by defining a collection of component classes and a set of parameters for component initialization. For example, component classes to be specified include the simulated nest network, the request generator to be used, and the ant algorithm to be simulated. Initialization parameters include the duration of the simulation, the network size, the failure probability, etc. This flexible configuration mechanism enable developers to build simulations  by assembling a collection of pre-defined and customized component classes, thus simplifying the process of evaluating ant algorithms.

Unlike other toolkits for multi-agent simulation, Anthill uses a single ant implementation in both the simulation and actual run-time environments, thus avoiding the cost of re-implementing ant algorithms before deploying them. This important feature has been achieved by a careful design of the Anthill API and by providing two distinct implementations of it for simulation and deployment.