Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Network Failure Detection and Graph Connectivity
Authors: Kleinberg, Jon
Sandler, Mark
Slivkins, Aleksandrs
Keywords: computer science
technical report
Issue Date: 22-Nov-2002
Publisher: Cornell University
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 edge-connectivity $\lambda$ and node-connectivity $\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 edge-cuts of a graph; for node failures, we develop a novel approach for working with the much more complex set of all minimum node-cuts of a graph.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File SizeFormat
2002-1886.ps337.14 kBPostscriptView/Open

Refworks Export

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


© 2014 Cornell University Library Contact Us