Computing the fault tolerance of multi-agent deployment

Yingqian Zhang; Efrat Manisterski; Sarit Kraus; V. S. Subrahmanian; David Peleg

doi:10.1016/j.artint.2008.11.007

Computing the fault tolerance of multi-agent deployment

Yingqian Zhang^*, Efrat Manisterski, Sarit Kraus, V. S. Subrahmanian, David Peleg

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

15 Scopus citations

Abstract

A deployment of a multi-agent system on a network refers to the placement of one or more copies of each agent on network hosts, in such a manner that the memory constraints of each node are satisfied. Finding the deployment that is most likely to tolerate faults (i.e. have at least one copy of each agent functioning and in communication with other agents) is a challenge. In this paper, we address the problem of finding the probability of survival of a deployment (i.e. the probability that a deployment will tolerate faults), under the assumption that node failures are independent. We show that the problem of computing the survival probability of a deployment is at least NP-hard. Moreover, it is hard to approximate. We produce two algorithms to accurately compute the probability of survival of a deployment-these algorithms are expectedly exponential. We also produce five heuristic algorithms to estimate survival probabilities-these algorithms work in acceptable time frames. We report on a detailed set of experiments to determine the conditions under which some of these algorithms perform better than the others.

Original language	English (US)
Pages (from-to)	437-465
Number of pages	29
Journal	Artificial Intelligence
Volume	173
Issue number	3-4
DOIs	https://doi.org/10.1016/j.artint.2008.11.007
State	Published - Mar 2009
Externally published	Yes

Funding

\u2729 This article is the extended version of the paper which appeared in the Second IEEE Symposium on Multi-Agent Security and Survivability [Y. Zhang, E. Manister, S. Kraus, V.S. Subrahmanian, Approximation results for probabilistic survivability, in: Second IEEE Symposium on Multi-Agent Security and Survivability, Philadelphia, USA, 2005, pp. 1\u201310]. This research was supported in part by the Technology Foundation STW, applied science division of NWO, and the Ministry of Economic Affairs of the Netherlands, by grant N6133906C0149, in part by ARO grant DAAD190310202, AFOSR grants FA95500610405, FA95500510298, NSF grant 0540216, NSF grant 0705587, and ISF grant 1685/07. * Corresponding author. E-mail addresses: [email protected] (Y. Zhang), [email protected] (E. Manisterski), [email protected] (S. Kraus), [email protected] (V.S. Subrahmanian), [email protected] (D. Peleg).

Keywords

Algorithms
Fault tolerance
Multi-agent deployment
Replication

ASJC Scopus subject areas

Language and Linguistics
Linguistics and Language
Artificial Intelligence

Access to Document

10.1016/j.artint.2008.11.007

Cite this

@article{73a0473cdf9841f887344240a21ff4f2,

title = "Computing the fault tolerance of multi-agent deployment",

abstract = "A deployment of a multi-agent system on a network refers to the placement of one or more copies of each agent on network hosts, in such a manner that the memory constraints of each node are satisfied. Finding the deployment that is most likely to tolerate faults (i.e. have at least one copy of each agent functioning and in communication with other agents) is a challenge. In this paper, we address the problem of finding the probability of survival of a deployment (i.e. the probability that a deployment will tolerate faults), under the assumption that node failures are independent. We show that the problem of computing the survival probability of a deployment is at least NP-hard. Moreover, it is hard to approximate. We produce two algorithms to accurately compute the probability of survival of a deployment-these algorithms are expectedly exponential. We also produce five heuristic algorithms to estimate survival probabilities-these algorithms work in acceptable time frames. We report on a detailed set of experiments to determine the conditions under which some of these algorithms perform better than the others.",

keywords = "Algorithms, Fault tolerance, Multi-agent deployment, Replication",

author = "Yingqian Zhang and Efrat Manisterski and Sarit Kraus and Subrahmanian, {V. S.} and David Peleg",

note = "Funding Information: ✩ This article is the extended version of the paper which appeared in the Second IEEE Symposium on Multi-Agent Security and Survivability [Y. Zhang, E. Manister, S. Kraus, V.S. Subrahmanian, Approximation results for probabilistic survivability, in: Second IEEE Symposium on Multi-Agent Security and Survivability, Philadelphia, USA, 2005, pp. 1–10]. This research was supported in part by the Technology Foundation STW, applied science division of NWO, and the Ministry of Economic Affairs of the Netherlands, by grant N6133906C0149, in part by ARO grant DAAD190310202, AFOSR grants FA95500610405, FA95500510298, NSF grant 0540216, NSF grant 0705587, and ISF grant 1685/07. * Corresponding author. E-mail addresses: [email protected] (Y. Zhang), [email protected] (E. Manisterski), [email protected] (S. Kraus), [email protected] (V.S. Subrahmanian), [email protected] (D. Peleg).",

year = "2009",

month = mar,

doi = "10.1016/j.artint.2008.11.007",

language = "English (US)",

volume = "173",

pages = "437--465",

journal = "Artificial Intelligence",

issn = "0004-3702",

publisher = "Elsevier B.V.",

number = "3-4",

}

TY - JOUR

T1 - Computing the fault tolerance of multi-agent deployment

AU - Zhang, Yingqian

AU - Manisterski, Efrat

AU - Kraus, Sarit

AU - Subrahmanian, V. S.

AU - Peleg, David

N1 - Funding Information: ✩ This article is the extended version of the paper which appeared in the Second IEEE Symposium on Multi-Agent Security and Survivability [Y. Zhang, E. Manister, S. Kraus, V.S. Subrahmanian, Approximation results for probabilistic survivability, in: Second IEEE Symposium on Multi-Agent Security and Survivability, Philadelphia, USA, 2005, pp. 1–10]. This research was supported in part by the Technology Foundation STW, applied science division of NWO, and the Ministry of Economic Affairs of the Netherlands, by grant N6133906C0149, in part by ARO grant DAAD190310202, AFOSR grants FA95500610405, FA95500510298, NSF grant 0540216, NSF grant 0705587, and ISF grant 1685/07. * Corresponding author. E-mail addresses: [email protected] (Y. Zhang), [email protected] (E. Manisterski), [email protected] (S. Kraus), [email protected] (V.S. Subrahmanian), [email protected] (D. Peleg).

PY - 2009/3

Y1 - 2009/3

N2 - A deployment of a multi-agent system on a network refers to the placement of one or more copies of each agent on network hosts, in such a manner that the memory constraints of each node are satisfied. Finding the deployment that is most likely to tolerate faults (i.e. have at least one copy of each agent functioning and in communication with other agents) is a challenge. In this paper, we address the problem of finding the probability of survival of a deployment (i.e. the probability that a deployment will tolerate faults), under the assumption that node failures are independent. We show that the problem of computing the survival probability of a deployment is at least NP-hard. Moreover, it is hard to approximate. We produce two algorithms to accurately compute the probability of survival of a deployment-these algorithms are expectedly exponential. We also produce five heuristic algorithms to estimate survival probabilities-these algorithms work in acceptable time frames. We report on a detailed set of experiments to determine the conditions under which some of these algorithms perform better than the others.

AB - A deployment of a multi-agent system on a network refers to the placement of one or more copies of each agent on network hosts, in such a manner that the memory constraints of each node are satisfied. Finding the deployment that is most likely to tolerate faults (i.e. have at least one copy of each agent functioning and in communication with other agents) is a challenge. In this paper, we address the problem of finding the probability of survival of a deployment (i.e. the probability that a deployment will tolerate faults), under the assumption that node failures are independent. We show that the problem of computing the survival probability of a deployment is at least NP-hard. Moreover, it is hard to approximate. We produce two algorithms to accurately compute the probability of survival of a deployment-these algorithms are expectedly exponential. We also produce five heuristic algorithms to estimate survival probabilities-these algorithms work in acceptable time frames. We report on a detailed set of experiments to determine the conditions under which some of these algorithms perform better than the others.

KW - Algorithms

KW - Fault tolerance

KW - Multi-agent deployment

KW - Replication

UR - http://www.scopus.com/inward/record.url?scp=58849140398&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58849140398&partnerID=8YFLogxK

U2 - 10.1016/j.artint.2008.11.007

DO - 10.1016/j.artint.2008.11.007

M3 - Article

AN - SCOPUS:58849140398

SN - 0004-3702

VL - 173

SP - 437

EP - 465

JO - Artificial Intelligence

JF - Artificial Intelligence

IS - 3-4

ER -

Computing the fault tolerance of multi-agent deployment

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this