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 journalArticlepeer-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 languageEnglish (US)
Pages (from-to)437-465
Number of pages29
JournalArtificial Intelligence
Volume173
Issue number3-4
DOIs
StatePublished - Mar 2009
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Computing the fault tolerance of multi-agent deployment'. Together they form a unique fingerprint.

Cite this