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, JonSandler, MarkSlivkins, Aleksandrs Keywords: computer sciencetechnical report Issue Date: 22-Nov-2002 Publisher: Cornell University Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR2002-1886 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. URI: http://hdl.handle.net/1813/5862 Appears in Collections: Computer Science Technical Reports

Files in This Item:

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