
eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1813/5862
Title:  Network Failure Detection and Graph Connectivity 
Authors:  Kleinberg, Jon Sandler, Mark Slivkins, Aleksandrs 
Keywords:  computer science technical report 
Issue Date:  22Nov2002 
Publisher:  Cornell University 
Citation:  http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR20021886 
Abstract:  We consider a model for monitoring the connectivity of a network subject to node or edge failures. In particular, we are concerned with detecting \emph{$(\vareps, k)$failures}: events in which an adversary deletes up to $k$ network elements (nodes or edges), after which there are two sets of nodes $A$ and $B$, each at least an $\vareps$ fraction of the network, that are disconnected from one another. We say that a set $D$ of nodes is an $(\vareps, k)$detection set if, for any $(\vareps, 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 $(\vareps, k)$detection set of size bounded by a polynomial in $k$ and $\vareps$, independent of the size of $G$. In this paper, we expose some relationships between bounds on detection sets and the edgeconnectivity $\lambda$ and nodeconnectivity $\kappa$ of the underlying graph. Specifically, we show that detection set bounds can be made considerably stronger when parametrized by these connectivity values. We show that for an adversary that can delete $\lambda$ edges, there is always an $(\vareps, \lambda)$detection set of size at most $\freps$, and an $(\vareps, \lambda)$detection set of minimum size can be computed in polynomial time. A crucial point is that this bound is independent not just of the size of $G$ but also of the value of $\lambda$. Our bounds extend to adversaries that can delete up to $k \lambda$ edges for $k > 1$. We also show an analogous bound of $O(\frac{1}{\vareps})$ on the size of detection sets for adversaries that can delete $\kappa$ nodes. Our algorithm for $(\vareps, \lambda)$edge failures is based on the cactus representation of all minimum edgecuts of a graph; for node failures, we develop a novel approach for working with the much more complex set of all minimum nodecuts of a graph. 
URI:  http://hdl.handle.net/1813/5862 
Appears in Collections:  Computer Science Technical Reports

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.
