CS 789 THEORY SEMINAR [home]

Speaker:  Aleksandrs Slivkins
Affiliation: Cornell
Date: Monday, November 10, 2003
Title: Network Failure Detection and Graph Connectivity

Abstract:

We are concerned with detecting (eps,k)-failures of a network: events in which an adversary deletes up to k nodes or edges, after which there are two sets of nodes A and B, each at least an eps-fraction of the network, that are disconnected from one another. We say that a set D of nodes is an (eps, k)-detection set if, for any (eps, k)-failure of the network, some two nodes in D are no longer able to communicate; in this way, D "witnesses" any such failure.

Recent results show that for any graph G, there is an (eps, k)-detection set of size bounded by a polynomial in k and eps, independent of the size of G. This set can be found efficiently using random sampling. In this paper, we show that the bounds on the size of a detection set (and on the sufficient #samples) can be made considerably stronger when parameterized by the edge-connectivity and node-connectivity of the underlying graph.

Joint work with Jon Kleinberg and Mark Sandler. To appear in SODA'04. Paper available from http://www.cs.cornell.edu/people/slivkins/research.