|
The Anthill Project |
|
Department of Computer Science University of Bologna Bologna, Italy |
Department of Telematics Norwegian University of Science and Technology Trondheim, Norway |
Anthill is supported by: |
Project Summary 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.
Project OverviewPeer-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. Project History and StatusThe Anthill project has started during Spring 2001. In September 2001, Anthill version 1.0 has been published. Anthill 1.1, published at the end of August 2002, has been extended to contain the JXTA runtime environment developed by a Master's student of the University of Bologna, Francesco Russo. The development of Anthill is now temporarily discontinued in favor of a more scalable and light-weight simulator, called Peersim. Peersim has been developed under the BISON project (Biology-Inspired techniques for Self Organization in dynamic Networks), funded by the European Commission. The aim of BISON is to explore the use of ideas derived from complex adaptive systems (CAS) to enable the construction of robust and self-organizing information systems for deployment in highly dynamic network environments such as Ad-Hoc and Virtual networks, P2P and Grid computing systems. The BISON partners include the Department of Computer Science at the University of Bologna (Italy), Telenor (Norwegian telecom company), the Interdisciplinary Center for High Performance Computing (ZHR) at Technical University of Dresden (Germany), the Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA) (Switzerland) and the Santa Fe Institute (USA). |