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

13 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

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