Probabilistically Survivable MASs

Abstract

Multiageht systems (MAS) can "go down" for a large number of reasons, ranging from system malfunctions and power failures to malicious attacks. The placement of agents on nodes is called a deployment of the MAS. We develop a probabilistic model of survivability of a deployed MAS and provide two algorithms to compute the probability of survival of a deployed MAS. Our probabilistic model does not make independence assumptions though ·such assumptions can be added if so desired. An optimal deployment of a MAS is one that mu:imizes its survival probability. We provide a mathematical answerto this question. an algorithm that computes an exact solution to this problem, as well as several algorithms that quickly compute approximate solutions to the problem. We have implemented our algorithms - our implementation demonstrates that computing deployments can be done scalably.