Probabilistically Survivable MASs

1 Introduction

As multiagent systems (MASs) are increasing used for crit­ ical applications, the ability of these MASs to survive intact when various external events occur (e.g. power failures, OS crashes, etc.) becomes increasingly important. However, one never knows when and if a system will crash or be compro­ mised, and hence, any model of MAS survivability must take this uncertainty into account.

We provide for the first time, a formal model for reasoning about survivability of MASs which includes both a declar­ ative theory of survivability, as well as implemented algo­ rithms to compute optimal ways of deploying MASs across a network.

A MAS-deployment specifies a placement of agents on various network nodes. Based on probabilistic information aboutthe survivability of a given node, we develop a formal

"The first author is also affiliated with UMIACS. This work wa.s supported in part by the Army Research Lab under contract DAAL 0197K0135, the CTA on Advanced Decision Architectures, by ARO contract DAAD190010484, by NSF grant IIS0222914 and an NSF ITR award 0205 489.

V.S. Subrabmanian and N. Ciban Ta~

Dept. of Computer Science University of Maryland College Park, MD 20742 { vs,ctas }@cs.umd.edu

theory describing the probability that a given deployment will survive. This probability reflects the best guarantee we have of the MAS surviving. Our model does not assume that node failures are independent, though independence information can be easily added if so desired. The technical problem we need to grapple with is that of finding a MAS -deployment of the agents having the highest probability of survival. As we do not make unrealistic independence assumptions, this prob­ lem turns out to be intractable. As a consequence, heuristics are required to find a deployment (even if it is sub-optimal). We develop algorithms for the following tasks:

1. Given a MAS-deployment, how do we compute its prob­ ability of survival?
2. Find a MAS-deployment with the highest probability of survival - this algorithm is infeasible to implement in practice due to the above mentioned complexity results.
3. We develop a suite of heuristic algorithms to find (sub­ optimal) MAS-deployments.

We have conducted detailed experiments with our algo­ rithms- for space reasons. only some of them are described here. The experiments show that our heuristic algorithms can find deployments very fast.

2 Preliminaries

Agents. The only assumptions we make about agents is that they provide one or more services. We further assume that all host computers on which agents are located have a ft. nite amount of memory resources. and that each (copy of an) agent a requires some amount of memory. denoted by mem(a). A multiagent application MAS is a finite set of agents- we make the assumption that all agents in a multi­ agent application are needed for it to function.

Networks. A network is a triple (N, edges, mem) where N is a set of called nodes, edges ~ N X N specifies which nodes can communicate with which other nodes. and mem : N -+ R specifies the total memory 1 available at node n for use by agents situated at n. A network is fully connected iff edges =N X N.

1 Note that the symbol mem is used to both denote the memory requirements of an agent, as well as the memory available at a node. It is easy to determine the intended meaning of this expression from context.

Definition 2.1 Suppose MAS is a multiagent application and Ne = (N,edges, mem) is a network. A deployment/or MAS on N e is a mapping Jl : N -+ 2M AS specifying which agents are located at a given node. (As usual, if X is a set, 2x is the power set of X). J1 must satisfy the following condition:

• (Va E MAS)(3n E N) a E p.(n). This condition says that every_ agent must be deployed somewhere.
• (Vn E N)mem(n) ~ EaEJJ(n)mem(a). This condition says that the agents deployed at a node cannot use more memory than that node makes available.

Intuitively, Jl(n) = { a1, a2} says that agents a1, a2 are de­ ployed at node n 1·

Example2.1 SupposeN = {n1,n2,n3,n4} and MAS {a,b,c,d}. An example deployment is given by: p,(nt) = {a,b}, p(n2) = {c,d}, Jl(n3) = {a.,b,c,d} and11(n4) = { d}. This example will be used throughout this paper.

3 Related Work

To our knowledge, there are no probabilistic models of sur­ vivability of a MAS. However, there are many works that are in related areas.

[Shehory et al., 1998] use agent-cloning and agent­ merging techniques to mitigate agent over-loading and pro­ mote system load balancing. Fan [Fan, 2001] proposes a BDI mechanism to formally model agent cloning to balance agent workload.

[Fedoruk and Deters, 2002] propose transparent agent replication technique- though an agent is represented by mul­ tiple copies, this is an internal detail hidden from other agents. Several otherframeworks also support this kind of agent fault tolerance [Mishra,2001].

[Marin et al., 2001] develop adaptive fault tolerance tech­ niques for MASs. They use simulations to assess migration and replication costs. However, [Marin eta/., 2001] con­ cludes by saying that they do not address the questions of which of the agents to replicate. how many replicas should be made, where those replicas should be allocated. These ques­ tions are addressed in the current paper, but we do not propose a mechanism to synchronize agent replications.

[Kumar eta!., 2000] focus on the problem of broker agents that are inaccessible due to system failures. They use the the­ ory of teamwork to specify robust broke red architectures that can recover from broker failure. We, on the other band, con­ sider the possible failure of any agent in the multi-agent sys­ tems.

The problem of network reliability has beenstudied exten­ sively- [Gartner, 1999] provide an excellent survey. In this paper we build on top of these studies and assume, as dis­ cussed below, that there is a disconnect probability function for a network specifying the reliability of each node of the network.

The problem of fault-tolerant software systems has some similarities to our agent survivability problem. An exten­ sive study was performed to solve this problem using theN­ Version Problem (NYP) approach. The NYP is defined as the "independent generation of N ~ 2 functionally equivalent programs from the same initial specification" [Lyu and He, 1993]. In this approach. the reliability of a software system is increased by developing several versions of special modules and incorporating them into a fault-tolerant system [Gutjahr, 1998]. However. these works (i) make unnecessary or unwar· ranted independence assumptions, (ii) provide only a measure of expected survivability rather than guaranteed survivability, (iii) do not consider replication.

4 A Probabllistic Model of Survivability

Multiagent applications can "go down" because nodes on which agents are located can crash. Alternatively, agents are on a mobile node (e.g. a vehicle) may wander beyond com· munications range, thus dropping out of the network.

Deftnitlon 4.1 A disconnect probability function for a net· work (N, edges, mem) is a mapping dp: N-+ C[O, 1] where C[O, 1] is the set of all closed subintervals of [0, 1].

Intuitively, if dp(N) = [0.2, 0.3], then this says that there is a 20 - 30% probability that node N will get disconnected from the network. Note that this model supports the sima· tion where we do not know the probability of node n get· ting disconnected- in this case, we can set dp(N) = (0, 1]. Likewise, if we know that a node will get disconnected with 80% probability with a ±3% margin of error. then we can set dp(n) = [0.77, 0.83]. One possibility to compute dp in a spe· cific setting is by collecting statistical data on the past failures of each node. This would give us both a mean probability of failure for a given node as well as a standard deviation which would jointly result in a probability interval. In other applica­ tions (e.g. where statistics are not available) expert opinions can be used.

Given a network (N,edges, mem) and a disconnect prob­ ability function dp, there is a space of possible networks that may arise in the future.

Deftnition 4.2 Suppose (N, edges, mem) is a network and N' ~ N. Then (N', edges', mem) is a possible future net­ work where edges' = {(n1 , n2 ) I (nt, n2 ) E edges and n1,n2 EN'}.

We use PFNdp(N, edges, mem) to denote the set of all possible future networks associated with a network (N, edges, mem) and a disconnect probability function dp. Note that we can infer probabilities of possible future net· works from such disconnect probabilities on nodes. Even though many future networks are possible at a given time t, only one of them will in fact occur at time t. So at time t, PFNdp(N, edges, mem) represents the space of pos· sible network configurations. Given a network Ne' = (N',edges',mem) we write N E Ne' iff N EN'. Fur· thermore, since in this paper we do not discuss the failure of edges, for space reasons, we will omit them from the net· works in the rest of the paper.

Suppose prob(Ne) denotes the probability of a possible future network Ne. For any N E N we can write the con· straint:

1 - dp(N).UB ~ ENe'EPFNd.(N',mem) 1\ NENe'prob(Ne') ~ 1- dp(N).LB.

This constraint says that the sum of the probabilities of all future networks in which node N survives must be between 1-dp(N) .UB and 1-dp(N).LB. We take all such constraints

(one for each node) and add a constraint which says that the only possible future networks are those in PFNdp(N, mem). Last. but not least, we know that the probability of each future network is at least 0. This gives us:

:ENe'EPFNdp(N,mem)Prob(Ne) = 1.

For any Ne' E PFNdp(N, mem), prob(Ne');::: 0.

If Ne = (N, mem). then CONS(dp ,Ne) denotes the set of all such constraints. 2 We can use CONS(dp, Ne) to de­ termine the survival probability of a given deployment.

Definition 4.3 Given a network N e, a disconnect probability function dp, and a deployment J.l, we say that the probability of survival of J.l is given by the following linear program: minimize E Ne'EPFNd· 1\ ~'is a deployment w.r.t.Ne'prob(N e') subject to CONS(dp, Ne) .

The so lutions of CONS( dp, N e) are possible probabilities of possible future networks arising. Clearly, any of these probability assignments is possible. The objective function above adds the probabilities of all possible future networks where at least one copy of each agent in MAS survives. This expression must be minimized because different solutions of CONS(dp, Ne) assign different values to this sum- as any of these solutions is possible, the only guarantee we can give about survivability of 11 is that it exceeds the minimal such value.

Computing Optimal Deployment (COD) Problem. Given a network Ne, and a disconnect probabi lity function dp, find a deployment whose probability of survival is maxi­ ma l.

This is the key problem that we will solve.

5 Computing the Survival Probability of a Deployment

A naive way to find the probability of survival of a given J.l is to solve the linear program of Definition 4.3 using classical linear programming algorithms [Hiller and Lieberman,l974: Karmarkar, 1984]. However, the size of the linear program involved in enormous. Our Compute Deployment Probability (CDP) algorithm will avoid this problem. CDP uses a func­ tion called Loc which takes an agent a, a network (N, mem), and a deployment 11 as input, and returns the set of all nodes N E N such that a E J.t(N) as output. One way of pruning the search is to use the following results.

Proposition 5.1 Suppose MAS is a multiagent application and N e is a network and suppose there is at least one multi­ agent application deployment for MAS on Ne. Furthersup­ posethatforal/agentsa, mem(a) > 0. Thenthereexistsan optimal multiagent deployment J.l (i.e. p has maximal prob­ ability of survival) such that for all agents a1 , a2, the set of locations of agent a1 according to J.l is not a strict subset of the set of locations of agent a2 according tort.

2 It is important to note that if, for example, we know that the dis· connect probabilities of n 1 and n2 arc independent, then we c11n e!l­ pand CONS( dp, N e) to include the constraint prob( { n1, n2}) = 1- dp(nl) * dp(n:z ). For sp11cc reasons, we do not go into this in further detail.

The above result says that when trying to find an optimal mul ­ tiagem deployment J.l. we must ensure that no agent is located in a set of nodes that is a strict subset of the set of nodes that another agent is located in. As we shall see, this property al­ lows us to prune our search a fair amount. Before describing our algorithm, we need to introduce some notation,

• An agent a is relevant w.r.t. J.l and Ne if there is no other agent which is deployed at a strict subset of nodes at which a is deployed. ra (N e, 11·) denotes the set of relevant agents w.r.t. 11, 1Ve.
• The necessary nodes of Ne w.r.t J.l is nn (Ne,Jl.) = {N I :la E ra(Ne , p.),N E Loc(a ,Ne,J.t) }. Nodes in which no relevant agents are deployed are not important.

The following theorem says that survivability is unaffected if we get rid of unnecessary nodes.

Theorem 5.1 Suppose MAS is a multiagent application, Ne = (N, mem) is a network, dp is a disconnect proba­ bility function and f.1 is a feasible multiagent application de­ ployment for MAS on N e. Let N e' = (N', mem) where N' = n n ( N e, 1-' ). If J.l 1 is the restriction of 11. to N e', then surv(p) = surv(J.t').

Proof Sketch. It is easy to see that it is enough to show the claim for the case that only one node is removed from N when constructing N e'. Without loss of generality, let us as­ sume that N' = N \ { N1 }. We make the following observa­ tions:

• It can be shown that N" ~ N' is feasible w.r.t J.l 1 iff N" U {Nt} is also feasible w.r.t fJ..
• Letn = INI. CONS(dp ,Ne) consistsofnequations. one for each node. CONS(dp, Ne 1 ) does not include an equation for N1 and thus includes n- 1 equations.
• We use prob (resp. prob 1 ) to denote the probability function in CONS(dp, Ne) (resp. CONS(dp , N e')). Consider the equations w.r.t. Ni E N. Ni =f. N1. For both Ne and N e 1 , both equations have the same left side, viz. 1 - dp(Ni)· The right side of the relevant equa­ tion in CONS(dp, Ne) consists of 2n-l elements of the form prob( {M} UN"}). N" ~ N \ {Ni}. In CONS(dp,Ne') the corresponding equation consists of 2n- 2 elements of the form prob'({Ni} UN"'}). N'" ~ N' \ {Ni}. Thus for each element in an equa­ tion of CONS(dp, Ne') of the form prob'(N") there are exactly two terms in the corresponding equation in CONS(dp,Ne): one of the form prob(N") and the otherofthe form prob(N" U {Nt}).
• Similarly. if the minimization expression with respect to N e' is of length (i.e. number of terms) k, then the min­ imization expression with respect to Ne is 2k. In par­ ticular, for each prob'(N") there are two terms in the minimization expression of the form prob'(N") and prob' (N" U { N1} ).

We are now ready to prove our claim. Suppose the min­ imization problem is solved with respect to N e. We set prob'(N") = prob(N") + prob(N" U {Nt}). It is easy to see that based on our observations that CONS(dp ,Ne')

will be satisfied and the values will minimize the relevant elt­ pression.

Suppose the minimization problem is solved wi th re­ spect to N e'. In this case, we add the following equa­ tions to CONS(dp , N e): (i) prob'(N ") = prob(N" ) + prob(N" U {Nt}) (ii) We replace each expression in the minimization expression of the form prob(N") + prob(N" U { N!}) by prob' (N"). It is easy to see that the minimization expression is identical to the one associated with N e' and all the constraints of CONS(dp , N e) except the first one are identical to those of CON S (dp ,N e') and are satisfied. Hence, it is left to show that the constraint asso­ ciated with N1 is satisfied.

This constraint is of the form : 1 - dp(Nt) = prob( {Nt} )+prob( {N1 , N2} )+ .. . +prob( {Nt , ... , Nn } ). We replace any term prob(N" U {Nt} ), N" ~ N' by prob'(N") - prob(N"). The sum of all the prob'(N") from the last constraint of CONS(dp,N e') is equal to l. Thus. we get that "'£N"Ciof' prob(N") = dp(Nt) where 0 ~ prob(N") ~ 1. As 0 ~ dp(Nt) ~ 1. this equation is solvable. D

The net impact of this theorem is that only necessary nodes need to be considered. We demonstrate this using Exam­ ple 2.1.

Example 5.1 Consider the deployment of Example 2.1 . Agent dis deployed at nodes {n2 , n 3 , n4 } and c is deployed at nodes { n2 , n 3 }. Clearly, cis deployed at a strict subset of nodes at which dis deployed. In order for the deployment to survive in a given possible future network one of the nodes on which c is located, n2 or n3 must stay connected. But then d will also be deployed in the new network. However; if n4 stays connected in a future network, but neither n2 nor n3 stay connected, the deployment will not survive. Thus, based on theorem 5.1 when computing the survivability of the de­ ployment, there is no need to consider d and n4.

We are now ready to use the above theorem to formulate our algorithm CDP to compute probability of survival of a de­ ployment. Our CDP algorithm will use the well known no­ tion of a hitting set.

Definition 5.1 SupposeS = {St , ... , Sn} is a set of sets. A hitting set for S is any seth ~ U~=t S; such that: (1) for a/ll ~ i ~ n, h n S; i= 0 and (2) there is no strict subset h' C h satisfying condition ( 1) above. HitSet(S) denotes the set of all hitting sets of S .

Hit Set can be implemented in any number of standard ways prevalent in the literature. We will focus on the following hitting sets with respect to a given network.

Definition 5.2 Suppose MAS is a multiagent application, N e = (N, mem) is a network and iJ. is a feasible multiagent application deployment for MAS on N e. The set of hitting sets with respect to MAS, N e and jJ. is hs(N e, jJ., MAS) = HitSet({Loc(a ,N e ,iJ.) I a E MAS}).

Intuitively, the hitting sets above describe minimal sets of nodes that must be present in a possible future network in order for the multiagent application to survive. We will use hitting sets to determine whether a deployment w.r.t. N e can be a deployment w.r.t. a possible future network. This intu­ ition leads to the following algorithm CDP.

Algorithm 5.1 (CDP(Ne,dp,MAS,t-t))

(* lnput :(l)A network N e = (N, mem)

(*

*)

(2) a disconnect probability function dp, -;c)

(*

(3) a multiagentapplication MAS

*)

(*

(4}afeasibledeploymentp.and

*)

• (* Output: the survivability of p..

*)

1. Pos.sNe = f/J; MAS' = ra(Ne, ft); ;V' = nn(Ne, p );
2. H = hs(N e', p.', MAS');
3. For anyN 11 E 2./lf' do
4. (a) t emp = H; fl ag = true;
5. (b) While t emp -:f. f/J and flag do
6. h = headof(temp); t emp = t emp \ h;
7. If h ~ N" then do
8. Pos.~Ne=Po.~.sNe U{(N", mem) };
9. flag= fals e;
10. Return the result of the following linear program: minimize :ENe"EPo .. Neprob(N e 11 ) subject to Cons(dp , N e 1 ).

CDP works by first focusing on the necessary nodes. Then, for each agent a E MAS', all nodes where that agent is lo­ cated are identified. It then computes all hitting sets of these nodes. For any possible future network it checks whether one of the hitting sets is a subset of the nodes of the network. It is easy to see that CDP is exponential in the number of the nec­ essary nodes. The following example illustrates the working of this algorithm.

Example 5.2 Consider the network, N e and the deploy­ ment iJ. of example 2 .1. Further; assume that dp(nr) = O.l ,dp(n2) = 0.2 , dp(n3) = 0.3 and dp(n4 ) = 0.4. ln the first step CDP sets MAS' = {a, c }, N' = { n t, n2, n 3 }.

There are 8 possible sets of nodes to be considered for fu· turenetworks: {Nt = {nt},N2 = {n2} ,N3 = {n3} ,N4 = {n1,n2},Ns = {nt , n3} ,Na {n2 ,n3},N7 {nt, n2, n3},Ns = 0}. Wedenotetheassociatednetworks by Ne1,Ne2, ... ,Nes.

In Step 2, CDP sets H = {ht , h2} where ht = {n t , n2} and h2 = { n 3 }. In step 3 b it checks which of the node sets of possible future networks are supersets of a hitting set of H and will also set PossNe = {Ne3 , Ne4 , N e5 , N e6 , N e7 }.

Denote prob(N e;) with Pi· The linear program to be solved in step4 is:

Minimize P3 + P4 + Ps + PG + P7 subject to the constraints: (1) Pt + P4 + Ps + P7 = 0.9 (2) P2 + P4 + Pa + P1 = 0.8 (3) P3 + Ps + PG + P1 = 0. 7 (4) IJt + P2 + P3 + P4 + Ps + Pa + P7 + Ps = 1 (5) Pi~ 0.

Using the linear programming tool Lindo, we found the fol­ lowing results: P7 = 0. 7, Pl = 0.2, P2 = 0.1, P3 = P4 = Ps = PG = Ps = 0 which yields the minimum value ofO. 7 for the objective function.

Example 5.3 In example 5.2, there were no constraints on the dependencies of the disconnect probabilities of the nodes. Suppose we know, in addition, that the probability that both nodes n 1 ,n3 get disconnected is 0.05, i.e. dp({n1 ,n3}) = 0.05. In this case we should consider all possible future net­ works whose set of nodes is not a superset of {n1 , ng}. Those sets are Nz and N8 of example 5.2. Thus, the new constraint is P2 + Ps = 0.05.

If we run the linear program of example 5.2 again with the additional constraint, the results are as follows : p4 = 0.05, Pa = 0.05, 1J? = 0.65, P1 = 0.2, P2 = 0.05, Ps = P3 = Ps = 0 which yields the minimum value of 0. 75 for the objective function.

6 Computing Optimal Deployments

We are now ready to develop algorimms to find an optimal multiagenr deployment. We first present the COD algorithm to compute optimal deployments. We also presenttwo heuris­ tic algorimms, HADl and HAD2, which may find subopti­ mal deployments (but do so very fast).

6.1 The COD Algorithm

One may wonder if COD can be solved via a classical prob­ lem such as facility location problem (FLP)[Shmoys et al., 19971. In FLP, there are a set of facility locations and a set of consumers. The task is to determine which facilities should be used and which customers should be served from which facil ity so as to minimize some objective function (e.g. sum of travel times for customers to their assigned facility). One may think that we can directly use FLP algorithms to solve COD - unfortunately, this is not true.

Theorem 6.1 The problem of checking if a MAD-deployment fJ is optimal is NPNP.hard.

This theorem says that even if we have a polynomial or­ acle to solve NP-complete problems, checking if a MAD­ deployment is optimal is still NP-hard I In fact, it is easy to reduce the facility location problem to mat of finding an optimal deployment. Even if we have an oracle for facility location, the MAD-deployment problem is still NP-hard.

Computing an optimal MAD-deployment involves two sources of complexity. The first is the exponential space of possible deployments. The second is that even if we have a given deployment, finding its probability of survival is expo­ nential.

Thus, to solve COD exactly. we do a state space search where the initial state places all agents in a multiagent appli­ cation MAS on all nodes of the network N e. lfthis placement is a deployment, then we are done. Otherwise, mere are many ways of removing agents from nodes and each such way leads to a possible deployment. The value of a state is the surviv­ ability of the state, which can be computed using me CDP algorimm. As soon as a deployment is found, we can bound the search using the value of that deployment. The reason is that given any state in the search, all states obtained from that state by removing one or more agent has a lower surviv­ ability than me original state. Before presenting me COD algorimm, we first present the SEARCH routine used by it.

Algorithm6.1 SEARCH (Ne,dp,MAS,j-t,best~" bestvat) (*Input:(l)A networkNe = (N, mem) (* (2) a disconnect probability function, dp

(*

(3) a multiagent application, MAS

*)

(*

(4) a deployment, It

*)

(*

(*

(*

(*

1. best deployment found so far, best~' (globalvariable)
2. best survivabilityvaluefound thus far, be.~tval (global variable)

*)

*)

*)

*)

• (*Output: The procedure changes the global variables *)

(*

be.~ tl"' and bc.~tva l

1. prob(J.L) =CDP(Ne,dp.J.L, MAS);
2. if( best,.al < prob(J.L)) then do
3. (a) if It satisfies the mem constraints then do
4. bcBtp. = 1],
5. best val = prob(ll)
6. (b) else do
7. For any N E N do
8. For any a E 1./,(N) do
9. ternp1" = It;
10. temp1"(N) = temp~'(N) \{a}
11. if tcmz>~' is a deployment then s earch(N e, dp, MAS , temp,., bestp., be.~tval)

We are now ready to present the COD algorimm.

Algorithm 6.2 COD(Ne,dp, MAS)

(*Input ; (l)AnetworkNe=(N,mem) *) (* (2) a disconnect probability function dp, *) (* (3) a multiagent application MAS *) (*Output : an optimal deployment *) 1. beBtl' =null; best val = 0 2. For any N EN do lt(N) = MAS;

1. search(N e, dp, MAS, J.L, bestp., bestval);
2. return bestp.

The correctness of COD depends on the correctness of bounding the search in step 2 of algorimm 6.1. We present the correctness result below.

Theorem 6.2 Suppose MAS is a multiagent application, N e = (N, mem) is a network and dp is a disconnect proba­ bility function. Then COD(N e, dp , MAS) returns an opti­ maldeploymentofMAS on N e.

The astute reader may notice that COP is computed for every placement. Many of these placements are very similar to each other. Hence, one may wonder whether it is possible to use the results of computing COP applied to a previous placement to a placement that is very similar to the previous placement. The two propositions below show mat this can be done.

Proposition 6.1 Suppose MAS is a multiagent application, Ne = (N, mem) is a network and dp is a disconnect proba­ bility function . Suppose the placement j-! 1 was obtained from the placement j-t in step 2(b)iA of algorithm 6.1 and suppose N e' = (N', mem), such that N' = nn(Ne, Ji) . Then the set of hitting sets with respect to JJ 1 and Ne' is a subset of the set of hitting sets with respect to /-! and N e. That is, hs(Ne' ,,l, MAS) ~ hs(Ne,j-t, MAS).

The following example demonstrate a situation where hs(Ne' , ~-t' , MAS) C hs(Ne,j-t , MAS).

*)

Example6.1 SupposeN = {n1 ,n2 ,n3 }, MAS= {a,lJ,c} andthedeploymentp,isasfollows: JL(nt) = {a,c}, 11 (n2) = {a,b} andJ;,(n,3) = {b}. Thus,Loc(a,Ne , fl) = {nt ,nz}, Loc(b,Ne,J;,) = {n2 ,n3 }, Loc(c,Ne,J;,) = {nt}. The hit­ ting sets are, h1 = {n1 ,n2}, h2 = {n1,n3}. lfwe remove agent a from node n 1, then the set h2 is no longer a hitting set.

Proposition 6.2 Suppose MAS is a multiagent application, Ne = (N, mem) is a network and dp is a disconnect proba­ bility function. Suppose the placement p 1 was obtained from the placement 11 in step 2(b )iA of algorithm 6.1 and suppose Ne 1 = (N', mem), such that N' = nn(Ne, J/ ). Suppose there ish E hs(Ne, 11, MAS) such that N E h but N ~ N'. Then, h ~ hs(N e, 1/, MAS).

We use the above propositions to give a new version. CD Pl. of the CDP algorithm.

Definition 6.1 Suppose MAS is a multiagent application, N e = (N, mem) and JJ. is a deployment. A set h <;; JV supports an agent a E MAS if there is N E h such that a E p(N).

CDPl is now defined below.

Algorithm 6.3 CDPl(Ne, dp, MAS,J..t,Hp,a*,N)]

Step 1 as in CDP.

1. lfHp::j:.0thcndo
2. (a) H = 0;
3. (b) For any hE Hp do If N II h or h \ {N} supports a· then H = H u (h n N');
4. else H = hs(Ne',f'· MAS');
5. 4 . For any N" E 2N do
6. (a) temp= H; flctg =true;
7. (b) While temp ::j:. 0 and flag do
8. h = headof(ternp); temp= tmnp \ h;
9. If h C ;V 11 then do
10. Po;sNc = Po.~$Ne U {(N", mem)};
11. fla,g = fa,lse;
12. Assign to IJ the result of the following linear program: minimize 'ENe"EPoHNeProb(Nt/') subject to Cons(dp, N c').
13. Return p and H;

The SEARCH and COD algorithms need to be modified in a straightforward way to use CDPl · we do not go through the details for space reasons.

6.2 Heuristic Algorithms

In this section, we describe two fast heuristic algorithms. HADl, HAD2. HADl iteratively solves knapsack prob· !ems [Cormen et al., 1990] by trying to pack nodes with low disconnect probability first.

Algorithm 6.4 HADl (Ne,dp,MAS)

• (*Input: As in algorithm COD (6.2).
• (*Output: a deployment

1. Jt = 0;jlag=true;
2. For all N EN do re.uwail(N) = mem(N);
3. While flag do

(a) node.~= N; (Lgents = MAS; flag= foLse;

• (b) While (node.~ ::j:. 0) do
• If agents = 0 then agent8 = MAS;
• N =argmindpnodcs;
• agent.sdq> = knap.H!.ck(N, mem_(wa.il(N), agent.s\ tt(N) );
• if agentsdop :f:. 0 then fl ag = t·rue;·
• 11-(N) = 1./, (N) U agent8dq>;
• re.Lavail(N) = re.s_ava.il(N)- "' mern(a); L....raEagcnt.!df'! Jl
• agent.s = agent.s \ agent.Sdep;
• nodes= node8 \ {N};

The HAD2 algorithm is based on the intuition that we should first locate agents with high resource requirements. and then deal with agents with low resource requirements. Thus, we sort agents in ascending order according to resource requirements, place them, then go to agents with the sec· ond highest resource requirements. and so on. If at the end resources are still available. then we make replicas of the agents.

Algorithm 6.5 HAD2(Ne,dp, MAS)

• (*Input and Output as in node-based-heuristic (HADJ) *)
• JL = 0;jlag=true;
• For all N EN res.LJvail(N)=mem(N);
• While flag do
• (a) node.s = N; agents= MAS; flag= fals e;
• (b) While (agent.~ :f. 0) do
• a=argrr~=m·magents
• nodesp0 ,. = {N I mem(a) ~ rc.s..avail(N)};
• if node.~po..., ::j:. 0 then do
• flag= true;
• N = argrnaxdpnode.spou;
• 11-(N) = JL(N) U {a};
• re.s_avail(N) = res_avail(N)- mem(a)
• agents= agents\ {a};

7 Experiments

We have implemented all the algorithms described in this pa· per. For space reasons, we only present experimental results on the heuristics for computing optimal deployments.

In our experiments. we varied the number of agents and the number of nodes. For each combination of agents and nodes. we ran several trials. In each trial, we randomly generated the memory available on each node. the node's disconnect probability, and the memory required for one copy of each agent. The experiments were conducted on a Linux box. us­ ing Red Hat 7.2 (Enigma). In all the experiments the number of nodes+ agents varied between 1 and 500. We randomly t .... ··················-------~~~~=-=-~-~~-~~~-==-~=--~

J

H..urt··ac CornP"'lrl.-on

genenned numbers between 0 and 0.5 as the disconnect prob­ ability of each node. The sizes of the agents were uniformly distributed between 3 and 9 (units of memory) and the sizes of the nodes were uniformly distributed between 5 and 30 (units of memory).

The top graph of figure 7 demonstrates the time efficiency of both heuristics: they can find a deployment for 500 agents and sites in under a second.

When comparing HADl and HAD2. we noticed that (see bottom graph of figure 7): (1) as the sum of the number of agents and nodes increases, the survivability decreases. (2) The node based heurisric almost always finds better deploy­ ments than the agent-based heuristic. In addition, (3) When there are more agents than nodes, the node based heuristic will require less time, while when there are more nodes than agents the agent based heuristic will take less time.

The intuition behind observation (1) is as follows. As the number of agents increases, it becomes more difficult to maintain the feasibility of the system, and thus survivability decreases. In addition, when the number of nodes increases, there are more possible future networks and thus, the prob­ ability that there will be one network with a low probability increases. Since, the survivability depends on the worst case. its value decreases.

8 Conclusions

As more and more agents are deployed in mission critical commercial, telecommunications, business, and financial ap-

I

plications, there is a growing need for guarantees that such multiagent applications will survive various kinds of catastro­ phes. The scope of the problem is so vast that any one paper can only make a small dent in this very important problem.

In this paper, we have carved out such a small piece of the problem. Specifically. we study the problem of how to deploy multiple copies of agents in a MAS on nodes so that the prob­ ability of survivability ofthe MAS is maximized. We provide a formal, mathematical model for probabilistic MAS surviv­ ability, and develop an optimal algorithm for this purpose as well as some heuristic algorithms. We have conducted exper­ iments showing the effectiveness of the approach.