Approximation results for probabilistic survivability

TitleApproximation results for probabilistic survivability
Publication TypeConference Papers
Year of Publication2005
AuthorsZhang Y, Manister E, Kraus S, V.S. Subrahmanian
Conference NameMulti-Agent Security and Survivability, 2005 IEEE 2nd Symposium on
Date Published2005/08//
Keywordsapplication;, computing;, failure;, fault, heuristic, heuristics, industrial, model;, multi-agent, multiagent, node, probabilistic, probability;, programming;, survivability;, system;, systems;, testing;, tolerant

As multiagent systems (MASs) are increasingly used in industrial applications, the need to make them more robust and resilient against disruption increases dramatically. The author 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.