Robust Networks

Add to your list(s) Download to your calendar using vCal

• Sanjeev Goyal, University of Cambridge, Economics Department
• Wednesday 19 November 2008, 14:15-15:15
• Lecture Theatre 1, Computer Laboratory.

If you have a question about this talk, please contact Timothy G. Griffin.

We study the architecture of networks which are robust to attacks by an intelligent adversary.

We start with a model in which designer chooses a network with a view to maximizing communication between nodes, and the adversary can choose to attack nodes. Our analysis focuses on a simple trade-off: better connected agents are more likely to succeed in completing the task. Monitoring on the part of the adversary however induces a cost to connecting agents since detection of a single node in the network may lead to the detection of other connected nodes. We first characterize optimal networks faced with a uniform attack probability of all nodes. We show that optimal networks are constituted of cells which increase in number (and decrease in size) as the intensity of monitoring grows. We then examine the optimality of uniform attack strategy: symmetric attacks are optimal if adversary has very large budgets, but asymmetric attacks are optimal otherwise. Interestingly, optimal networks are constituted of equal size cells, irrespective of adversary budget size!

We then allow for designer to choose a network as well as to defend individual nodes. The robustness of networks now depends on the efficacy of defense and attack technologies. If nodes can be made attack-proof and designer has small budgets then star network and its variants are optimal.

This talk is part of the Wednesday Seminars - Department of Computer Science and Technology series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Chris Davis' list
• Department of Computer Science and Technology talks and seminars
• Graduate-Seminars
• Guy Emerson's list
• Interested Talks
• Lecture Theatre 1, Computer Laboratory
• School of Technology
• Trust & Technology Initiative - interesting events
• Wednesday Seminars - Department of Computer Science and Technology
• bld31
• computer science
• se393's list

Note that ex-directory lists are not shown.