Network Failure Detection and Graph Connectivity

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.