Approximation results for probabilistic survivability

Yingqian Zhang*, Efrat Manister, Sarit Kraus, V. S. Subrahmanian

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


As multiagent systems (MASs) are increasingly used in industrial applications, the need to make them more robust and resilient against disruption increases dramatically. Kraus et al [1] has developed a probabilistic model (assuming complete ignorance of dependencies between node failures) of survivability based on deploying each agent in a MAS on one or more nodes. Finding a deployment that maximizes survivability is highly intractable for two reasons: firstly, computing the survivability of any deployment is intractable, and secondly, going through an exponential number of deployments to find the best one adds another layer of intractability. In this paper, we study what happens when node failures are independent. We show that computing survivability in this environment is still intractable. We propose various heuristics to compute the survivability of a given deployment. We have implemented and tested all these heuristics. We report on the advantages and disadvantages of different heuristics in different environmental settings.

Original languageEnglish (US)
Title of host publication2005 IEEE 2nd Symposium on Multi-Agent Security and Survivability
Number of pages10
StatePublished - 2005
Externally publishedYes
Event2005 IEEE 2nd Symposium on Multi-Agent Security and Survivability - Philadelphia, PA, United States
Duration: Aug 30 2005Aug 31 2005

Publication series

Name2005 IEEE 2nd Symposium on Multi-Agent Security and Survivability


Conference2005 IEEE 2nd Symposium on Multi-Agent Security and Survivability
Country/TerritoryUnited States
CityPhiladelphia, PA

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Approximation results for probabilistic survivability'. Together they form a unique fingerprint.

Cite this