Fault-tolerant replication in networks with asynchronous communication link failures

We investigate the problem of locating data replicas in a network in order to maximize data availability. In particular, we analyze the complexity of computing optimal placements in networks in which communication link failures are asynchronous (i.e., only a single link fails at a time.) We show that placements maximizing availability for read operations minimize the status of the subtree induced by the data copies in the network component tree. It is observed that the optimal placement problem for read operations corresponds to two network optimization problems that have previously been studied, and thus existing polynomial algorithms for these problems can be used to compute optimal placements efficiently. We then present new results for the problem of determining optimal placements for write operations. It is shown that this problem can be formulated as a packing optimization problem, and that this problem is NP-complete.