Minimum congestion redundant assignments to tolerate random faults
We consider the problem of computing minimum congestion, fault-tolerant, redundant assignments of messages to faults, parallel delivery channels, In particular, we are given a set K of faulty channels, each having an integer capacity c(i) and failing independently with probability f(i). We are also given a set M of messages to be delivered over K, and a fault-tolerance constraint (1 - epsilon), and we seek a redundant assignment phi that minimizes congestion Cong(phi), i.e. the maximum channel load, subject to the constraint that, with probability no less than (1 - epsilon), all the messages have a copy on at least one active channel. We present a polynomial-time 4-approximation algorithm for identical capacity channels and arbitrary message sizes. and a 2[ln(\K\/epsilon)/ln(1/f(max))]-approximation algorithm for related capacity channels and unit size messages. Both algorithms are based on computing a collection {K-1, ..., K-v} of disjoint channel subsets such that, with probability no less than (1 - epsilon), at least one channel is active in each subset. The objective is to maximize the sum of the minimum subset capacities. Since the exact version of this problem is NP-complete, we provide a 2-approximation algorithm for identical capacities, and a polynomial-time (8 + o(1))-approximation algorithm for arbitrary capacities.
redundant assignments fault-tolerance polynomial-time approximation algorithms