Locating Servers for Reliability and Affine Embeddings
Kenneth A. Berman · SIAM Journal on Discrete Mathematics · 2007
Consider the problem of locating servers in a network for the purpose of storing data, performing an application, etc., so that at least one server will be available to clients even if up to k component failures occur throughout the network. Letting $G = (V,E)$ be the graph with vertex set V and edge set E representing the topology of the network, and letting $L \subseteq V$ be a set of potential locations for the servers, a fundamental problem is to determine a minimum-size set $S \subseteq L$ such that the network remains connected to S even if up to k component failures occur throughout the network. We say that such a set S is k-fault-tolerant. In this paper we present an algebraic characterization of k-fault-tolerant sets in terms of affine embeddings of G in k-dimensional Euclidean space. Employing this characterization, we present a polynomial-time Monte Carlo algorithm for computing a minimum-size k-fault-tolerant subset S of L. In fact, we solve the following more general problem for directed networks: given a digraph $G = (V,E)$ (an undirected graph is equivalent to a symmetric digraph) and a subset $L \subseteq V$, we find a k-fault-tolerant subset S of L having minimum cost, where a unary integer cost $c(v)$ is associated with locating a server at vertex $v \in V$.