Fault tolerance is an important property of large-scale multi-agent systems as the failure rate grows with both the number of the hosts and deployed agents, and the duration of computation. Several approaches have been introduced to deal with some aspects of the faulttolerance problem. However, most existing solutions are ad hoc. Thus, no existing multi-agent architecture or platform provides a fault-tolerance service that can be reused to facilitate the design and implementation of reliable multi-agent systems. So, we have developed a faulttolerant multi-agent platform (named DimaX) which deals with fail-stop failures like bugs and/or break down machines. It brings fault-tolerance for multi-agent applications by using replication techniques. It is based on a replication framework (named DARX).
The present section aims at defining the type of failures DimaX deals with. Then, it presents the DimaX services for developing fault-tolerant MAS. 2.1
The most generally accepted failure classification can be found in [
Given this classification, two types of failure models are usually considered in distributed
environments [
In this work we focus on the fail-silent model. An agent failure is defined as its abnormal termination due to failure in an underlying resource. This could be either a bug in the underlying operating system, or a local host crash or a network disconnection. 2.2
DimaX is the result of an integration of a multi-agent platform (named DIMA[
One of the problem related to multi-agent systems distribution is the agent localization at the time of message sending. A naming server maintains the list (i.e., white pages) of all the agents within its administration domain. When an agent is created, it is registered at both the DimaX server and the naming server. To send messages to another, an agent needs to know the application-level identifier of the receiver. However, the transmission of these messages through DimaX servers, requires some knowledge about the physical localization (i.e., the IP address and a port number). The local DimaX server requests this information from the naming server and locally stored it in a cache. So, the cache contains the list of agents which have been contacted. This avoids that a DimaX server repeats several times the same search.
Agents Replication Service Naming
Service Failure Detection
Service
Observation
Service
Control Application
(DIMA) Middleware
(DARX) Failure detection is an essential aspect of any fault-tolerant system; indeed it is necessary to recognize a faulty agent. DARX fault detection service is based on the heartbeat technique; a process sends an I am alive message to other processes for informing that it is safe (see Figure 2). This technique has two parameters: • the heartbeat period: the time between two emissions of the I am alive message, • the timeout delay: the time between the last reception of an I am alive message from p and the time where q suspects p, until an I am alive message from p is received.
The detection results may be incorrect; q detects that p is crashed while p is actually safe but its
transmissions are delayed for some reason (e.g., communication load). To overcome this problem,
one solution is to estimate the arrival date of the following I am alive message, with a dynamic
margin. These values are functions of the quality of service of the network and the application [
When a server detects a failure of another DimaX server, its naming module removes all the replicated agents the faulty server hosted from the list and replaces these agents by their replicas located on other hosts. The replacement is initiated by the failure notification.
HeartBeat Period P
Q FAULT DETECTION
AT Q
Delay Timeout SAFE
Delay Timeout
FAULTY
Delay Timeout
SAFE The functionalities of the observation service are fundamental for controlling replication. An observation module collects data at two levels: • system level: data about the execution environment of the MAS like CPU time and mean time between failures, • application level: information about its dynamic characteristics like the interaction events among agents (e.g., the sent and received messages).
The observation service relies on an organization of reactive agents (named host- and agentmonitors) (see Figure 3). An agent-monitor is associated to each agent of the application (named domain agents) and a host monitor is associated to each host. These monitoring agents (agentmonitors and host-monitors) are hierarchically organized. Each agent-monitor communicates only with one host-monitor. Host-monitors exchange their local information to build global information (global number of messages, global exchanged quantity of information, . . . ).
After each interval of time Δt, the host-monitor sends the collected events and data to the
corresponding agent-monitors. When the criticality 1 of the domain agent is significantly
modified, the agent-monitor notifies its host-monitor. The latter informs the other host-monitors to
update global information. In turn, agent-monitors are informed by their host-monitor when global
information changes significantly (see [
l Agent_Monitor1 e v e L n o i t a v r e s b O l e v e L t en Domain Agent1 g A
Agent_Monitor2 Domain Agent2
Agent_Monitor3
Agent_Monitor4
Agent_Monitor5 Host_Monitor i Host_Monitor j SendMessage Event
Control Domain Agent3
Domain Agent4
Domain Agent5
Replication is an effective way to achieve fault tolerance in distributed systems. It has proved its
efficiency [
Active replication strategies provide fast recovery but lead to a high overhead. If the degree of replication is n, the n replicas are activated simultaneously. Passive replication minimizes processor utilization by activating redundant replicas only in case of failures. That is: if the active replica is found to be faulty, a new replica is elected among the set of passive ones and the execution is restarted from the last saved state. This technique requires less CPU resources than the active one but it needs a checkpoint management which remains expensive in processing time and space.
Many toolkits (e.g., see [
1The criticality of an agent, regarding an organization of agents it belongs to, is the measure of the potential impact of the failure of that individual agent on the failure of the whole organization 2.3
Replication has been successfully applied to several distributed applications. These distributed applications are characterized by a small number of components and the criticality of these components is often static. So, the number of replicas and the replication strategy are explicitily and statically defined by the designer before runtime. However, multi-agent applications are more complex than traditional distributed ones. They have dynamic organizational structures, adaptive behaviors of agents and a large number of agents. So, the criticality of agents may evolve dynamically during the course of computation. Our solution is a control mechanism of replication which decides, dynamically, which agent should be replicated and with what strategy (how many replicas and where to create the replicas). This control mechanism dynamically estimates the agents’ criticality. We have experimented two strategies based on organizational concepts to estimate the criticality of an agent.
The first strategy we studied is based on the concept of role. A role, within an organization,
represents a pattern of services, activities and relations. As such, it captures some information about
the relative importance of roles and their interdependencies. A role analysis thus represents the
set of interaction events resulting from the domain agent interactions (sent and received messages).
These events are then used to determine the roles of the agent. This strategy is described in [
The class AgentBehavior and its subclasses represent the internal activity of the agent. The instance method proactivityLoop() (see Table 2.4.1), used by startup, defines the basic loop of 2.4.1
DIMA is a Java multi-agent platform. Its kernel is a framework of proactive components which represent autonomous and proactive entities. A simple DIMA agent architecture consists of: a proactive component, an agent engine, and a communication component (see Figure 4).
A proactive component (the AgentBehavior class) represents an autonomous and proactive entity. It provides the basic structure to represent behaviors. The main functionalities of a proactive component may be extended in the subclasses. An instance of AgentBehavior describes: • The goal of the proactive component, it is implicilty or explicitly described by the method isAlive(). • The basic behaviors of the proactive component. A behavior is a sequence of actions that allow to change the internal state or to send a message to other components. the agents. An Agent Engine is provided to launch and support the agent activity. AgentEgine implements Runnable. In the latter, the method run has been redefined: public class AgentEngine extends ProactiveComponentEngine implements Runnable { protected ProactiveComponent proactivity; public Thread thread; } public void run(){ proactivity.startUp(); }
Methods public abstract boolean isAlive() public abstract void step() void proactivityLoop()
Description Tests if the agent has not reached its goal.
Represents an execution cycle of the agent.
Represents the control of agent behavior. public void startUp() public void proactivityLoop() { while (this.isAlive()) { this.preActivity(); this.step(); this.postActivity();} } Initializes and activates the control of agent behavior. public void startUp() { this.proactivityInitialize(); this.proactivityLoop(); this.proactivityTerminate();}
DIMA also provides several services like the directory facilitator service. DIMA can be used easily to build MASs. To make them reliable, we realized an integration of DIMA agents and DarX tasks. Before desccribing the result of this integration, we define the DarX tasks. 2.4.2
DARX [
The TasKShell sends outgoing messages through its encapsulated DarXCommInterface. The communication between distinct TaskShells is performed via a proxy: the RemoteTask (see Figure 7).
Thus, the sender of a message does not need to know the replicas number of the receiver; the RemoteTask of the receiver delegates the messages to the corresponding TaskShell which transmits them to all replicas of the same agent. The replication has a cost in communication but DARX optimizes it by piggybacking application-level messages on the I am alive messages (see Section 2.2.2).
DarX task
TaskShell + DarXTaskEngine
run() +startTask() +terminateTask() C C + + DarXomomponent sendMessage() receiveMessage() Figure 6 gives the main classes to model fault-tolerant agents. As the DarXTask is an active entity and each fault-tolerant agent needs to have the structure of a DarXTask, the DarXTask needs to be autonomous and proactive. To make the DarXTask autonomous, we encapsulate the DIMA agent behavior into the DarXTask (see Figure 7). This agent architecture enables to replicate the agent several times. As the DARX middleware and the DIMA platform both provide mechanisms for execution control, communication and naming but at different levels, their integration requires a set of some additional components; This set calls, transparently, for DARX services (e.g., replication, naming) when executing multi-agent applications developed with DIMA; at the application level, any code modification is required. It controls the execution of agents built under DimaX and offers a communication interface between remote agents, through DimaX servers.
Duplicated Messages
TaskShell RemoteTask (group proxy) request buffer
reply DarXCommInterface
reply buffer
DarXMessage: − sender: agentID − content: DIMA message ssseaeg DarXTaskEngine AM (A Specific DarX Task) M I D
DIMA Agent
Behavior DarXTaskExecutor t n e n o p m o C n o iti a c n u m m o C X ra
D
A DimaX agent is a DIMA agent encapsulated in a particular entity, the DarXTaskEngine. + C ommunicatingAgentBehavior activate() ++activateWithDarX() step() readAllMessage() ++sendMessage() +
AgentFact -csotueppl(e):Vector -+isresliult()
Ave():bool +proactivityInitialize() +
AgentMult -csotueppl(e):Vector +multiply() The DarXTaskEngine is a DarXTask, with autonomous behaviors of the original DIMA agent. It includes the agent engine (called the DarXTaskExecutor) which executes the lifecycle of the agent (see below the proactivityLoop method). For coherence reasons, the execution of the agent lifecycle may be suspended during the creation and/or updates of the replicas. When a DimaX agent sends messages to other agents, DimaX provides communication mechanisms to localize agents and deliver them messages. This delivery is realized through the communication component of DimaX agents (DarXComComponent) which delegates the DIMA message transmissions to the associated DarXCommInterface. This communication interface enables DARX entities to communicate between them. So, at the application level, the agents communicate DIMA messages which are transmitted via the DARX middleware. 3
The aim of DimaX is to augment an already built MAS with fault-tolerance capabilities. So, this section presents a MAS which has been developed by DIMA and shows how to make it fault tolerant.
To exemplify DimaX, we propose the Factorial toy problem (n!). This toy problem gives some insights to distributed problem solving. We consider two kinds of agents: 1. AgentFact: these agents have the needed behavior to compute a factorial but they do not have the behavior to multiply numbers. 2. AgentMult: these agents have a behavior to compute a multiplication.
These agents are implemented as subclasses of CommunicatingAgentBehavior class (see Figure 8). To compute n!, AgentFact creates a list (named couple) with the numbers from 1 to n: pubilc void proactivityInitialize(){ for (int i=1, i<=n, i++){ couple.addElement(i); } } pubilc void result(int i){ couple.addElement(i); // nbRequests is the number of resquests nbRequests --; }
Then, it sends requests to AgentMult with all possible couples of numbers. When it receives a result, it puts it into the list:
If the list has more than one element, new requests are then sent to AgentMult. It repeats this action while the list contains more than one number or AgentFact has not the responses to all the sent requests. This test is performed by its isAlive() method as follows: pubilc boolean isAlive(){ return ((couple.size() > 1) or not(hasAllResponses())); }
The AgentFact behavior is defined by: pubilc void step(){
readAllMessages(); while (couple.size()>1) { sendMessage(‘‘multiply’’,couple.elementAt(0), couple.elementAt(1),new AgentName(‘‘multiplier’’)); couple.remove(0); couple.remove(1); nbRequests++;} }
The AgentMult behavior is as follows: public void step(){ readAllMessages(); }
The multiply action of MultAgent is: public void multiply(int a, int b){ int c=a*b; sendMessage(‘‘result’’,c, new AgentName(‘‘factorial’’));} }
The initialization of the MAS is performed as: public void main (String [] args) { // agents behavior initialization AgentFact a= new AgentFact(‘‘factorial’’); AgentMult b=new AgentMult(‘‘multiplier’’);
// agents activation on the same machine a.activate(); b.activate(); }
After the designer builds the agents behavior by using the DIMA multi-agent platform, he/she uses the activateWithDarX method to deploy his/her MAS and to endow it with fault-tolerance capabilities (i.e., replication). This activation method enables to encapsulate the agent behavior in a DarXTask (see Section 2.4) and register the agent in the system (i.e., the naming service). Its parameters are the url and port of the host where the agent will be replicated. The deployment can be performed as follows: public void main (String [] args) { AgentFact a= new AgentFact(‘‘factorial’’); AgentMult b=new AgentMult(‘‘multiplier’’); // agents activation on two different machines a.activateWithDarX(url1, port1); b.activateWithDarX(url2, port2); }
As we can see, the distribution and replication have not required any code modification. The distribution cost is therefore minimal. Thus, DimaX facilitates the development of fault-tolerant MAS for developers not trained in fault-tolerance techniques. They need only to focus on problem solving issues like the agents behavior and their interactions. The factorial example is very simple. However, the solution is similar even if the application is more complex.
This section presents DimaX main features which are provided to the development and deployment
of fault-tolerant large-scale MAS: scalability, reusability, robustness, and adaptability.
1. Scalability. A platform is said to be scalable if it can handle the increasing of the problem
size (number of agents) and complexity without suffering a noticeable loss of performance.
In DimaX, the proposed solution is to organize hierarchically the components of the
different services in order to minimize the communication overload caused by them. DimaX also
provides global state of MAS (e.g., the average number of exchanged messages), in a
distributed manner. Indeed, this reduces remote access and avoids bottleneck, contrary to the
case of a central component. Moreover, the messages used by the failure detection service are
piggybacked by the other services messages and those of the application.
2. Reusability. To faciliate the design and implementation of fault-tolerant large-scale MAS,
for developers not trained in fault-tolerance techniques, DimaX provides several component
libraries to build multi-agent systems: decision components, communication components,
interaction protocols. For example, the library of interaction protocols provides a generic
implementation of interaction protocols. Interaction protocols are resuable components.
3. Robustness. The robustness of MAS is almost always a major concern when they are applied
to critical domains like spacecraft, or medicine. It is important that this kind of application
runs without interruption, in spite of failures, like crashes. DimaX achieves robustness of
MASs by using adaptive replication mechanisms. To evaluate the reliability of the platform,
we have run the robustness test based on fault injection techniques. The results show that
our platform achieves a robustness degree interesting of the application. Also, the platform
must continue to deliver its services in despite of one of its services components failure. The
failure of a machine or a connection often involves the failure of the associated DimaX server.
However, in our solution, the fault tolerance protocols are agent-dependent and not-place
dependent, i.e., the mechanisms built for providing the continuity of the computation are
integrated in the replication groups, and not in the server.
4. Adaptability. To deal with limited resource problem for replicating agents, a good replication
mechanism should adapt the replication strategy to the evolution of the environment. Thus,
we have introduced, in DimaX, a multiagent monitoring architecture to control replication.
This architecure implements our adaptation mechanisms to define the agent criticality. These
mechanisms rely on organizational concepts like role and interdependence graph [
In the multi-agent literature [
Kumar et al. [
Cougaar [
The FATMAS methodology [
A. Fedoruk and R. Deters [
In this paper, we presented a new fault-tolerant multiagent platform named DimaX. The design and the implementation of fault tolerant large scale multiagent systems require to deal with problems related to distribution and fault-tolerance. For that, DimaX provides several services namely naming service for agent localization, fault detection service for reconginizing faulty agents, observation service for collecting relevant information, and replication service for supporting replication techniques. Thanks to these services and their implementation, DimaX has interesting features like scalability, reusability, robustness, and adaptability for fault-tolerant MAS development. Thus, we achieve robustness by using replication techniques. Contrary to other approaches (i.e., diagnosis), replication enables us to run the critical multiagent applications without interruption. Moreover, our control of replication enables to change dynamically replication strategies, for better adapting to the evolution of the MAS context.
To generalize our approach, the futur work will propose a design methodology for fault-tolerant large-scale MAS. The principles developed in our approach to the failure problem in MAS will be the basis of the methodology.